# 一文秒杀所有丑数系列问题

Info

**已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~**

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode | Difficulty |
---|---|

1201. Ugly Number III | 🟠 |

263. Ugly Number | 🟢 |

264. Ugly Number II | 🟠 |

313. Super Ugly Number | 🟠 |

Prerequisites

Before reading this article, you should learn:

Recently, a reader in our group messaged me, saying they encountered a series of math-related algorithm questions during a Microsoft interview and felt overwhelmed. Upon reviewing the questions, I realized they were modified versions of the "Ugly Number" series problems on LeetCode.

Firstly, the "Ugly Number" series falls into the category of "easy for those who know, hard for those who don't," as it involves some mathematical theorems. If you haven't studied these specifically, it's unlikely you'll figure them out on your own.

Moreover, these problems heavily test abstract thinking and associative skills. Not only do they require mathematical theorems, but you also need to abstract the problem into linked list-related questions using two-pointer techniques, or into array-related questions using binary search techniques.

Today, I'll cover all "Ugly Number" related problems in one article, exploring how these problems can vary and how to solve them.

## Ugly Number I

First up is LeetCode problem 263, "Ugly Number." The problem asks you to determine if a given number `n`

is an "ugly number." An "ugly number" is a positive integer that only contains the prime factors `2`

, `3`

, and `5`

.

The function signature is as follows:

`boolean isUgly(int n)`

For example, 12 = 2 x 2 x 3 is an ugly number, while 42 = 2 x 3 x 7 is not an ugly number.

This problem is actually very simple, provided you know the Fundamental Theorem of Arithmetic (Unique Prime Factorization Theorem):

**Any natural number greater than 1 is either a prime number itself or can be factored into a product of prime numbers**.

Since any positive integer greater than one can be factored into a product of prime numbers, an ugly number can also be factored into a product of prime numbers, and these prime numbers can only be 2, 3, or 5.

With this understanding, you can implement the `isUgly`

function:

```
class Solution {
public boolean isUgly(int n) {
if (n <= 0) return false;
// if n is an ugly number, its factors should only be 2, 3, 5
while (n % 2 == 0) n /= 2;
while (n % 3 == 0) n /= 3;
while (n % 5 == 0) n /= 5;
// if it can be successfully factored, it is an ugly number
return n == 1;
}
}
```

```
class Solution {
public:
bool isUgly(int n) {
if (n <= 0) return false;
// if n is an ugly number, its factors should only be 2, 3, 5
while (n % 2 == 0) n /= 2;
while (n % 3 == 0) n /= 3;
while (n % 5 == 0) n /= 5;
// if it can be successfully factored, it is an ugly number
return n == 1;
}
};
```

```
class Solution:
def isUgly(self, n: int) -> bool:
if n <= 0:
return False
# if n is an ugly number, the factors should only be 2, 3, 5
while n % 2 == 0:
n //= 2
while n % 3 == 0:
n //= 3
while n % 5 == 0:
n //= 5
# if it can be successfully factored, it is an ugly number
return n == 1
```

```
func isUgly(n int) bool {
if n <= 0 {
return false
}
// if n is an ugly number, its factors should only be 2, 3, 5
for n % 2 == 0 {
n /= 2
}
for n % 3 == 0 {
n /= 3
}
for n % 5 == 0 {
n /= 5
}
// if it can be successfully factored, it is an ugly number
return n == 1
}
```

```
var isUgly = function(n) {
if (n <= 0) return false;
// if n is an ugly number, its factors should only be 2, 3, 5
while (n % 2 == 0) n /= 2;
while (n % 3 == 0) n /= 3;
while (n % 5 == 0) n /= 5;
// if it can be successfully factored, it is an ugly number
return n == 1;
};
```

## Ugly Number II

Let's increase the difficulty. Look at LeetCode problem #264 "Ugly Number II". Now, the task is not to determine if a number is an ugly number, but given an input `n`

, you need to find the `n`

-th ugly number. The function signature is as follows:

`int nthUglyNumber(int n)`

`int nthUglyNumber(int n)`

`def nthUglyNumber(n: int) -> int:`

`func nthUglyNumber(n int) int {}`

`var nthUglyNumber = function(n) {}`

For example, if the input is `n = 10`

, the function should return 12. This is because the sequence of ugly numbers from smallest to largest is `1, 2, 3, 4, 5, 6, 8, 9, 10, 12`

, and the 10th ugly number is 12 (note that we count 1 as an ugly number).

This problem is quite clever. It may seem like a math problem, but it actually involves merging multiple sorted linked lists and uses the idea of sieving prime numbers.

First, in a previous article How to Efficiently Find Prime Numbers, I discussed the "sieve method" for efficiently finding prime numbers: a prime number multiplied by any number other than 1 is not a prime number. By sieving out these numbers, the remaining ones are prime.

This image from Wikipedia illustrates it well:

Based on the sieve method for prime numbers and the definition of ugly numbers, we can easily deduce a pattern: **if a number x is an ugly number, then x * 2, x * 3, x * 5 are also definitely ugly numbers**.

If we imagine all ugly numbers as a sorted linked list from smallest to largest, it would look like this:

`1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 8 -> ...`

Then, we can categorize ugly numbers into three types: multiples of 2, multiples of 3, and multiples of 5. These three types of ugly numbers are like three sorted linked lists, as follows:

Ugly numbers divisible by 2:

`1*2 -> 2*2 -> 3*2 -> 4*2 -> 5*2 -> 6*2 -> 8*2 ->...`

Ugly numbers divisible by 3:

`1*3 -> 2*3 -> 3*3 -> 4*3 -> 5*3 -> 6*3 -> 8*3 ->...`

Ugly numbers divisible by 5:

`1*5 -> 2*5 -> 3*5 -> 4*5 -> 5*5 -> 6*5 -> 8*5 ->...`

If we merge these three "sorted linked lists" together and remove duplicates, we get the sequence of ugly numbers. The `n`

-th element in this sequence is the answer we want:

`1 -> 1*2 -> 1*3 -> 2*2 -> 1*5 -> 3*2 -> 4*2 ->...`

So, this is similar to the approach discussed in Summary of Two-Pointer Techniques for Linked Lists for merging two sorted linked lists. Let's first look at the core solution code for merging sorted linked lists:

```
ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// Virtual head node to store the result list, pointer p points to the result list
ListNode dummy = new ListNode(-1), p = dummy;
// p1, p2 are on two sorted lists respectively
ListNode p1 = l1, p2 = l2;
while (p1 != null && p2 != null) {
// Compare the two pointers p1 and p2
// Connect the node with the smaller value to the result list
if (p1.val > p2.val) {
p.next = p2;
p2 = p2.next;
} else {
p.next = p1;
p1 = p1.next;
}
// Pointer p keeps moving forward
p = p.next;
}
// Some non-core code is omitted...
}
```

```
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
// Create a dummy node to store the result list, p pointer points to the result list
ListNode* dummy = new ListNode(-1), *p = dummy;
// p1, p2 are on two sorted lists respectively
ListNode* p1 = l1, *p2 = l2;
while (p1 != nullptr && p2 != nullptr) {
// Compare the two pointers p1 and p2
// Connect the node with the smaller value to the result list
if (p1->val > p2->val) {
p->next = p2;
p2 = p2->next;
} else {
p->next = p1;
p1 = p1->next;
}
// Move the p pointer forward continuously
p = p->next;
}
// Some non-essential code is omitted...
}
```

```
def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
# create a dummy node to store the result linked list, pointer p points to the result linked list
dummy = ListNode(-1)
p = dummy
# p1, p2 are on two ordered linked lists respectively
p1 = l1
p2 = l2
while p1 and p2:
# compare the two pointers p1 and p2
# connect the node with the smaller value to the result linked list
if p1.val > p2.val:
p.next = p2
p2 = p2.next
else:
p.next = p1
p1 = p1.next
# p pointer keeps moving forward
p = p.next
# omit some non-core code...
```

```
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
// a dummy node to store the result linked list, pointer p points to the result linked list
var dummy = &ListNode{-1, nil}, p = dummy
// p1, p2 are on two sorted linked lists respectively
var p1 = l1
var p2 = l2
for p1 != nil && p2 != nil {
// compare the two pointers p1 and p2
if p1.Val > p2.Val {
p.Next = p2
p2 = p2.Next
} else {
p.Next = p1
p1 = p1.Next
}
// connect the node with the smaller value to the result linked list
p = p.Next
}
// pointer p keeps moving forward
// omit some non-core code...
}
```

```
function mergeTwoLists(l1, l2) {
// create a dummy node to store the result linked list, pointer p points to the result linked list
var dummy = new ListNode(-1), p = dummy;
// p1, p2 are on two ordered linked lists respectively
var p1 = l1, p2 = l2;
while (p1 != null && p2 != null) {
// compare the two pointers p1 and p2
// connect the node with the smaller value to the result linked list
if (p1.val > p2.val) {
p.next = p2;
p2 = p2.next;
} else {
p.next = p1;
p1 = p1.next;
}
// pointer p keeps moving forward
p = p.next;
}
// omit some non-core code...
}
```

For this problem, we abstract out three ordered lists of ugly numbers. Merging these three ordered lists gives us the sequence of ugly numbers, where the `n`

-th ugly number is the answer the problem seeks.

Similar to merging two ordered lists, here is the solution code for this problem:

```
class Solution {
public int nthUglyNumber(int n) {
// can be understood as three pointers pointing to the head of the ordered list
int p2 = 1, p3 = 1, p5 = 1;
// can be understood as the value of the head node of the three ordered lists
int product2 = 1, product3 = 1, product5 = 1;
// can be understood as the final merged ordered list (result list)
int[] ugly = new int[n + 1];
// can be understood as the pointer on the result list
int p = 1;
// start merging the three ordered lists, and end when the nth ugly number is found
while (p <= n) {
// take the smallest node from the three lists
int min = Math.min(Math.min(product2, product3), product5);
// connect the smallest node to the result list
ugly[p] = min;
p++;
// move the pointer forward on the corresponding ordered list
if (min == product2) {
product2 = 2 * ugly[p2];
p2++;
}
if (min == product3) {
product3 = 3 * ugly[p3];
p3++;
}
if (min == product5) {
product5 = 5 * ugly[p5];
p5++;
}
}
// return the nth ugly number
return ugly[n];
}
}
```

```
class Solution {
public:
int nthUglyNumber(int n) {
// can be understood as three pointers to the head nodes of ordered linked lists
int p2 = 1, p3 = 1, p5 = 1;
// can be understood as the values of the head nodes of the three ordered linked lists
int product2 = 1, product3 = 1, product5 = 1;
// can be understood as the final merged ordered linked list (result list)
vector<int> ugly(n + 1);
// can be understood as the pointer on the result linked list
int p = 1;
// start merging the three ordered linked lists, end when the nth ugly number is found
while (p <= n) {
// take the smallest node from the three lists
int min_val = min({product2, product3, product5});
// connect the smallest node to the result linked list
ugly[p] = min_val;
p++;
// move the pointer forward on the corresponding ordered linked list
if (min_val == product2) {
product2 = 2 * ugly[p2];
p2++;
}
if (min_val == product3) {
product3 = 3 * ugly[p3];
p3++;
}
if (min_val == product5) {
product5 = 5 * ugly[p5];
p5++;
}
}
// return the nth ugly number
return ugly[n];
}
};
```

```
class Solution:
def nthUglyNumber(self, n: int) -> int:
# understand as three pointers pointing to the head of ordered linked lists
p2, p3, p5 = 1, 1, 1
# understand as the values of the head nodes of the three ordered linked lists
product2, product3, product5 = 1, 1, 1
# understand as the final merged ordered list (result list)
ugly = [0] * (n + 1)
# understand as the pointer on the result list
p = 1
# start merging the three ordered lists and end when the nth ugly number is found
while p <= n:
# take the smallest node from the three lists
min_val = min(product2, product3, product5)
# attach the smallest node to the result list
ugly[p] = min_val
p += 1
# move forward the pointer of the corresponding ordered list
if min_val == product2:
product2 = 2 * ugly[p2]
p2 += 1
if min_val == product3:
product3 = 3 * ugly[p3]
p3 += 1
if min_val == product5:
product5 = 5 * ugly[p5]
p5 += 1
# return the nth ugly number
return ugly[n]
```

```
func nthUglyNumber(n int) int {
// can be understood as three pointers pointing to the head nodes of ordered linked lists
p2, p3, p5 := 1, 1, 1
// can be understood as the values of the head nodes of the three ordered linked lists
product2, product3, product5 := 1, 1, 1
// can be understood as the final merged ordered linked list (result linked list)
ugly := make([]int, n+1)
// can be understood as the pointer on the result linked list
p := 1
// start merging the three ordered linked lists, and end when the nth ugly number is found
for p <= n {
// take the smallest node among the three linked lists
min := min(min(product2, product3), product5)
// connect the smallest node to the result linked list
ugly[p] = min
p++
// move the pointer forward on the corresponding ordered linked list
if min == product2 {
product2 = 2 * ugly[p2]
p2++
}
if min == product3 {
product3 = 3 * ugly[p3]
p3++
}
if min == product5 {
product5 = 5 * ugly[p5]
p5++
}
}
// return the nth ugly number
return ugly[n]
}
func min(a, b int) int {
if a < b {
return a
} else {
return b
}
}
```

```
var nthUglyNumber = function(n) {
// can be understood as three pointers pointing to the head nodes of ordered linked lists
let p2 = 1, p3 = 1, p5 = 1;
// can be understood as the values of the head nodes of the three ordered linked lists
let product2 = 1, product3 = 1, product5 = 1;
// can be understood as the final merged ordered linked list (result list)
let ugly = new Array(n + 1);
// can be understood as the pointer on the result linked list
let p = 1;
// start merging the three ordered linked lists, and end when the nth ugly number is found
while (p <= n) {
// take the smallest node from the three lists
let min = Math.min(Math.min(product2, product3), product5);
// attach the smallest node to the result list
ugly[p] = min;
p++;
// move the corresponding pointer on the ordered linked list
if (min == product2) {
product2 = 2 * ugly[p2];
p2++;
}
if (min == product3) {
product3 = 3 * ugly[p3];
p3++;
}
if (min == product5) {
product5 = 5 * ugly[p5];
p5++;
}
}
// return the nth ugly number
return ugly[n];
};
```

**We use p2, p3, p5 to represent pointers on three ugly number lists, product2, product3, product5 to represent the values of nodes on the ugly number lists, and the ugly array to record the results after merging the ordered lists**.

With the previous铺垫 and analogies, you should find it easy to understand the approach to this problem. Let's now increase the difficulty a bit.

## Super Ugly Number

Take a look at LeetCode problem 313, "Super Ugly Number." This problem gives you a list of prime numbers `primes`

and a positive integer `n`

, and asks you to calculate the `n`

-th "super ugly number." A super ugly number is a positive integer whose prime factors are all in the `primes`

list. The function signature is as follows:

`int nthSuperUglyNumber(int n, int[] primes)`

`int nthSuperUglyNumber(int n, int* primes)`

`def nthSuperUglyNumber(n: int, primes: List[int]) -> int:`

`func nthSuperUglyNumber(n int, primes []int) int {}`

`var nthSuperUglyNumber = function(n, primes) {}`

If `primes = [2, 3, 5]`

, it refers to the previous problem, so this problem is an advanced version of the last one.

However, the approach is still similar. You still treat each prime factor as a sorted linked list. The previous problem was equivalent to merging three sorted linked lists, while this problem is like merging `len(primes)`

sorted linked lists. This is the same idea as the "Merge K Sorted Lists" discussed in Double Pointer Techniques to Solve Seven Linked List Problems.

Note that in the previous problem, we abstracted three linked lists and needed `p2, p3, p5`

as pointers on these sorted linked lists. We also needed `product2, product3, product5`

to record the values of the nodes pointed to by these pointers. In each loop, we used the `min`

function to calculate the smallest head node.

In this problem, it's like we have `len(primes)`

sorted linked lists as input. We can't use the `min`

function to find the smallest head node anymore. Instead, we need to use a priority queue to calculate the smallest head node. We still need to maintain the linked list pointers and the values of the nodes they point to. We can use a triplet to store this information.

By combining the idea of merging K sorted linked lists from Double Pointer Techniques to Solve Seven Linked List Problems, you can understand the solution to this problem:

```
class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
// the priority queue contains triples long[] {product, prime, pi}
// where product represents the value of the list node, prime is the prime factor needed to calculate the next node, and pi is the pointer on the list
PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> {
// the priority queue is sorted by the value of the node
return (int)(a[0] - b[0]);
});
// add the head nodes of multiple lists to the priority queue
for (int i = 0; i < primes.length; i++) {
pq.offer(new long[]{ 1, primes[i], 1 });
}
// can be understood as the finally merged ordered list (result list)
long[] ugly = new long[n + 1];
// can be understood as the pointer on the result list
int p = 1;
while (p <= n) {
// take the smallest node of the three lists
long[] pair = pq.poll();
long product = pair[0];
long prime = pair[1];
int index = (int)pair[2];
// avoid duplicate elements in the result list
if (product != ugly[p - 1]) {
// connect to the result list
ugly[p] = product;
p++;
}
// generate the next node and add it to the priority queue
long[] nextPair = new long[]{ugly[index] * prime, prime, index + 1};
pq.offer(nextPair);
}
return (int)ugly[n];
}
}
```

```
class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
// the priority queue holds the triplet {product, prime, pi}
// where product represents the value of the list node, prime is the prime factor needed to calculate the next node, and pi is the pointer on the list
priority_queue<vector<long>, vector<vector<long>>, greater<vector<long>>> pq;
for (int i = 0; i < primes.size(); i++) {
pq.push({1, primes[i], 1});
}
// can be understood as the finally merged sorted list (result list)
vector<long> ugly(n + 1);
// can be understood as the pointer on the result list
int p = 1;
while (p <= n) {
// take the smallest node of the three lists
vector<long> pair = pq.top();
pq.pop();
long product = pair[0];
long prime = pair[1];
int index = pair[2];
// avoid duplicate elements in the result list
if (product != ugly[p - 1]) {
// connect to the result list
ugly[p] = product;
p++;
}
// generate the next node and add it to the priority queue
pq.push({ugly[index] * prime, prime, index + 1});
}
return ugly[n];
}
};
```

```
class Solution:
def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
# the priority queue holds triples {product, prime, pi}
# where product represents the value of the list node, prime is the prime factor needed to calculate the next node, and pi is the pointer on the list
pq = []
for prime in primes:
heapq.heappush(pq, [1, prime, 1])
# can be understood as the finally merged sorted list (result list)
ugly = [0] * (n + 1)
# can be understood as the pointer on the result list
p = 1
while p <= n:
# take the smallest node of the three lists
product, prime, index = heapq.heappop(pq)
# avoid duplicate elements in the result list
if product != ugly[p - 1]:
# attach to the result list
ugly[p] = product
p += 1
# generate the next node and add it to the priority queue
heapq.heappush(pq, [ugly[index] * prime, prime, index + 1])
return ugly[n]
```

```
func nthSuperUglyNumber(n int, primes []int) int {
// the priority queue holds triples {product, prime, pi}
// where product represents the value of the list node, prime is the prime factor needed to calculate the next node, and pi is the pointer on the list
pq := make(PriorityQueue, 0)
for i := 0; i < len(primes); i++ {
heap.Push(&pq, []int64{1, int64(primes[i]), 1})
}
// can be understood as the final merged sorted list (result list)
ugly := make([]int64, n+1)
// can be understood as the pointer on the result list
p := 1
for p <= n {
// take the smallest node of the three lists
pair := heap.Pop(&pq).([]int64)
product := pair[0]
prime := pair[1]
index := pair[2]
// avoid duplicate elements in the result list
if product != ugly[p-1] {
// connect to the result list
ugly[p] = product
p++
}
// generate the next node and add it to the priority queue
heap.Push(&pq, []int64{ugly[index] * prime, prime, index + 1})
}
return int(ugly[n])
}
type PriorityQueue [][]int64
func (pq PriorityQueue) Len() int {
return len(pq)
}
func (pq PriorityQueue) Less(i, j int) bool {
return pq[i][0] < pq[j][0]
}
func (pq PriorityQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
}
func (pq *PriorityQueue) Push(x interface{}) {
*pq = append(*pq, x.([]int64))
}
func (pq *PriorityQueue) Pop() interface{} {
old := *pq
n := len(old)
x := old[n-1]
*pq = old[0 : n-1]
return x
}
```

```
var nthSuperUglyNumber = function(n, primes) {
// the priority queue contains triples {product, prime, pi}
// where product represents the value of the linked list node, prime is the prime factor needed to calculate the next node, and pi is the pointer on the linked list
let pq = new MinPriorityQueue({ priority: (pair) => pair[0] });
for (let prime of primes) {
pq.enqueue([1, prime, 1]);
}
// can be understood as the finally merged ordered list (result list)
let ugly = new Array(n + 1);
// can be understood as the pointer on the result list
let p = 1;
while (p <= n) {
// take the smallest node of the three lists
let pair = pq.dequeue().element;
let product = pair[0];
let prime = pair[1];
let index = pair[2];
// avoid duplicate elements in the result list
if (product != ugly[p - 1]) {
// connect to the result list
ugly[p] = product;
p++;
}
// generate the next node and add it to the priority queue
pq.enqueue([ugly[index] * prime, prime, index + 1]);
}
return ugly[n];
};
```

Preventing int Overflow

For strongly typed languages like Java/C++/Go, be cautious of `int`

type overflow.

Although the problem states that the `n`

-th super ugly number will not exceed the int upper limit `2^31 - 1`

, overflow can still occur when calculating `ugly[index] * prime`

. Therefore, use `long`

or `int64`

types to store the triplets.

Next, let's look at the fourth ugly number problem, which is the highlight of today.

## Ugly Number III

This is LeetCode problem #1201 "Ugly Number III". Here's the problem statement:

You are given four integers: `n, a, b, c`

. Design an algorithm to find the `n`

-th ugly number. An ugly number is a positive integer that is divisible by `a`

, `b`

, or `c`

.

The difference between this problem and previous ones is that it changes the definition of an "ugly number". As long as a positive integer `x`

has any of `a, b, c`

as a factor, `x`

is considered an ugly number.

For example, if the input is `n = 7, a = 3, b = 4, c = 5`

, the algorithm should output 10. The sequence of ugly numbers meeting the criteria is `3, 4, 5, 6, 8, 9, 10, ...`

, and the 7th number in this sequence is 10.

With the foundation from the previous problems, you can surely think of abstracting the multiples of `a, b, c`

into three ordered linked lists:

```
1*3 -> 2*3 -> 3*3 -> 4*3 -> 5*3 -> 6*3 -> 7*3 ->...
1*4 -> 2*4 -> 3*4 -> 4*4 -> 5*4 -> 6*4 -> 7*4 ->...
1*5 -> 2*5 -> 3*5 -> 4*5 -> 5*5 -> 6*5 -> 7*5 ->...
```

Next, merge these three linked lists into a single sorted linked list and remove duplicate elements. The resulting linked list will be the sequence of ugly numbers. From this sequence, we can find the `n`

-th element:

`1*3 -> 1*4 -> 1*5 -> 2*3 -> 2*4 -> 3*3 -> 2*5 ->...`

With this approach, you can directly write the code:

```
class Solution {
public int nthUglyNumber(int n, int a, int b, int c) {
// can be understood as the value of the head node of three ordered linked lists
// since the data size is large, use long type
long productA = a, productB = b, productC = c;
// can be understood as the pointer on the merged ordered linked list
int p = 1;
long min = -666;
// start merging the three ordered linked lists to get the value of the nth node
while (p <= n) {
// take the smallest node of the three linked lists
min = Math.min(Math.min(productA, productB), productC);
p++;
// move the pointer of the linked list corresponding to the smallest node
if (min == productA) {
productA += a;
}
if (min == productB) {
productB += b;
}
if (min == productC) {
productC += c;
}
}
return (int) min;
}
}
```

```
class Solution {
public:
int nthUglyNumber(int n, int a, int b, int c) {
// can be understood as the value of the head node of three ordered linked lists
// since the data size is large, use the long type
long productA = a, productB = b, productC = c;
// can be understood as the pointer on the merged ordered linked list
int p = 1;
long minProduct = -666;
// start merging the three ordered linked lists to get the value of the nth node
while (p <= n) {
// take the smallest node of the three linked lists
minProduct = min({productA, productB, productC});
p++;
// move the pointer of the corresponding linked list of the smallest node
if (minProduct == productA) {
productA += a;
}
if (minProduct == productB) {
productB += b;
}
if (minProduct == productC) {
productC += c;
}
}
return (int) minProduct;
}
};
```

```
class Solution:
def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
# can be understood as the value of the head node of three ordered linked lists
productA, productB, productC = a, b, c
# can be understood as the pointer on the merged ordered linked list
p = 1
min_product = -666
# start merging the three ordered linked lists to get the value of the nth node
while p <= n:
# take the smallest node among the three linked lists
min_product = min(productA, productB, productC)
p += 1
# move the pointer of the corresponding linked list of the smallest node
if min_product == productA:
productA += a
if min_product == productB:
productB += b
if min_product == productC:
productC += c
return min_product
```

```
func nthUglyNumber(n int, a int, b int, c int) int {
// can be understood as the value of the head node of three ordered linked lists
productA, productB, productC := a, b, c
// can be understood as the pointer on the merged ordered linked list
p := 1
minProduct := -666
// start merging the three ordered linked lists to get the value of the nth node
for p <= n {
// take the smallest node among the three linked lists
minProduct = min(min(productA, productB), productC)
p++
// move forward the pointer of the corresponding linked list of the smallest node
if minProduct == productA {
productA += a
}
if minProduct == productB {
productB += b
}
if minProduct == productC {
productC += c
}
}
return minProduct
}
func min(a, b int) int {
if a < b {
return a
} else {
return b
}
}
```

```
var nthUglyNumber = function(n, a, b, c) {
// can be understood as the value of the head node of three ordered linked lists
let productA = a, productB = b, productC = c;
// can be understood as the pointer on the merged ordered linked list
let p = 1;
let minProduct = -666;
// start merging the three ordered linked lists to get the value of the nth node
while (p <= n) {
// take the smallest node from the three linked lists
minProduct = Math.min(productA, productB, productC);
p++;
// move the pointer of the corresponding linked list forward for the smallest node
if (minProduct == productA) {
productA += a;
}
if (minProduct == productB) {
productB += b;
}
if (minProduct == productC) {
productC += c;
}
}
return minProduct;
};
```

This approach should be very simple, but it doesn't pass all test cases after submission; it times out.

Note that the data range given in the problem is very large, with `a, b, c, n`

potentially reaching 10^9. Therefore, even though the time complexity of the above algorithm is `O(n)`

, it is relatively time-consuming, and there should be a better approach to further reduce the time complexity.

**The correct solution to this problem is quite challenging. The difficulty lies in combining some mathematical knowledge with binary search techniques to efficiently solve the problem**.

First, we can define a monotonically increasing function `f`

:

`f(num, a, b, c)`

calculates the number of integers in the range `[1..num]`

that are divisible by `a`

, `b`

, or `c`

. Obviously, the return value of function `f`

increases as `num`

increases (monotonically increasing).

**The problem asks us to find the n-th number that is divisible by a, b, or c. In other words, we need to find the smallest num such that f(num, a, b, c) == n**.

This `num`

is the `n`

-th number that is divisible by `a`

, `b`

, or `c`

.

Based on the approach template provided in Practical Applications of Binary Search, we have a monotonically increasing function `f`

. To find the minimum value of the parameter `num`

, we can apply the binary search algorithm for finding the left boundary:

```
int nthUglyNumber(int n, int a, int b, int c) {
// the problem states that the result is within the range [1, 2 * 10^9],
// so we initialize the search range with both ends closed according to this range
int left = 1, right = (int) 2e9;
// binary search for the left boundary
while (left <= right) {
int mid = left + (right - left) / 2;
if (f(mid, a, b, c) < n) {
// there are not enough elements meeting the criteria in [1..mid], so the target is on the right half
left = mid + 1;
} else {
// the number of elements meeting the criteria in [1..mid] is greater than n, so the target is on the left half
right = mid - 1;
}
}
return left;
}
// function f is a monotonic function
// calculate how many numbers in [1..num] can be divided by a, b, or c
long f(int num, int a, int b, int c) {
// implementation below
}
// ... other code
```

```
int nthUglyNumber(int n, int a, int b, int c) {
// The problem states that the result is within the range [1, 2 * 10^9],
// so we initialize the search range with both ends closed according to this range
int left = 1, right = 2e9;
// binary search for the left boundary
while (left <= right) {
int mid = left + (right - left) / 2;
if (f(mid, a, b, c) < n) {
// there are not enough elements that meet the condition in [1..mid], so the target is on the right half
left = mid + 1;
} else {
// the number of elements that meet the condition in [1..mid] is greater than n, so the target is on the left half
right = mid - 1;
}
}
return left;
}
// function f is a monotonic function
// calculate how many numbers in [1..num] can be divided by a, b, or c
long f(int num, int a, int b, int c) {
// implementation below
}
// ... other code
```

```
def nthUglyNumber(n: int, a: int, b: int, c: int) -> int:
# the problem states that the result is within the range [1, 2 * 10^9],
# so we initialize the search range with both ends closed according to this range
left, right = 1, int(2e9)
# binary search for the left boundary
while left <= right:
mid = left + (right - left) // 2
if f(mid, a, b, c) < n:
# there are not enough elements that meet the condition in [1..mid], so the target is in the right half
left = mid + 1
else:
# the number of elements that meet the condition in [1..mid] is greater than n, so the target is in the left half
right = mid - 1
return left
# function f is a monotonic function
# calculate how many numbers between [1..num] can be divided by a or b or c
def f(num: int, a: int, b: int, c: int) -> int:
# implementation below
pass
# ... other code
```

```
func nthUglyNumber(n int, a int, b int, c int) int {
// the problem statement says the result is within the range [1, 2 * 10^9],
// so we initialize the search range with both ends closed according to this range
left, right := 1, int(2e9)
// binary search for the left boundary
for left <= right {
mid := left + (right - left) / 2
if f(mid, a, b, c) < n {
// there are not enough elements meeting the condition in [1..mid], so the target is in the right half
left = mid + 1
} else {
// the number of elements meeting the condition in [1..mid] is greater than n, so the target is in the left half
right = mid - 1
}
}
return left
}
// function f is a monotonic function
// calculate how many numbers in [1..num] can be divided by a or b or c
func f(num int, a int, b int, c int) int {
// implementation below
}
// ... other code
```

```
var nthUglyNumber = function(n, a, b, c) {
// the problem states that the result is within the range [1, 2 * 10^9],
// so we initialize the search range with both ends closed according to this range
let left = 1, right = 2 * 10 ** 9;
// binary search for the left boundary
while (left <= right) {
let mid = left + Math.floor((right - left) / 2);
if (f(mid, a, b, c) < n) {
// there are not enough elements that meet the condition in [1..mid], so the target is in the right half
left = mid + 1;
} else {
// the number of elements that meet the condition in [1..mid] is greater than n, so the target is in the left half
right = mid - 1;
}
}
return left;
};
// function f is a monotonous function
// calculate how many numbers in [1..num] can be divided by a or b or c
var f = function(num, a, b, c) {
// implementation below
};
// ... other code
```

The binary search code template for finding the left boundary was discussed in Binary Search Framework Explanation. There's not much to add there. The key point is how to implement the function `f`

, which involves set theory theorems and methods for calculating the least common multiple (LCM) and greatest common divisor (GCD).

First, let's define the set `A`

as the numbers in `[1..num]`

that are divisible by `a`

, set `B`

as those divisible by `b`

, and set `C`

as those divisible by `c`

. Therefore, `len(A) = num / a`

, `len(B) = num / b`

, and `len(C) = num / c`

, which is straightforward.

However, the value of `f(num, a, b, c)`

is not simply `num / a + num / b + num / c`

. This is because some numbers may be divisible by two or all three of `a, b, and c`

, as shown in the diagram below:

**According to set theory, the elements in this set should be: A + B + C - A ∩ B - A ∩ C - B ∩ C + A ∩ B ∩ C**. This should be clear with the help of the diagram.

The question arises, how do we calculate the number of elements in intersections like `A ∩ B`

?

It's actually quite simple. **The number of elements in A ∩ B is num / lcm(a, b), where lcm is the function to calculate the least common multiple**.

Similarly, the number of elements in `A ∩ B ∩ C`

is `num / lcm(lcm(a, b), c)`

.

Now, how do we find the least common multiple?

Just remember this theorem: ** lcm(a, b) = a * b / gcd(a, b), where gcd is the function to calculate the greatest common divisor**.

Next, how do we find the greatest common divisor? This is a classic algorithm, commonly known as the Euclidean algorithm (or辗转相除算法 in Chinese).

With all these nested concepts, we can finally translate this logic into code to implement the `f`

function. Note that due to the large data size in this problem, sometimes we need to use the `long`

type to prevent `int`

overflow:

```
class Solution {
public int nthUglyNumber(int n, int a, int b, int c) {
// the problem states that the result is within the range [1, 2 * 10^9],
// so initialize the search range with both ends closed according to this range
int left = 1, right = (int) 2e9;
// binary search for the left boundary
while (left <= right) {
int mid = left + (right - left) / 2;
if (f(mid, a, b, c) < n) {
// the number of elements that meet the condition in [1..mid] is less than n, so the target is on the right half
left = mid + 1;
} else {
// the number of elements that meet the condition in [1..mid] is greater than n, so the target is on the left half
right = mid - 1;
}
}
return left;
}
// calculate the greatest common divisor (Euclidean algorithm)
long gcd(long a, long b) {
if (a < b) {
// ensure a > b
return gcd(b, a);
}
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
// least common multiple
long lcm(long a, long b) {
// the least common multiple is the product divided by the greatest common divisor
return a * b / gcd(a, b);
}
// calculate how many numbers between [1..num] can be divided by a or b or c
long f(int num, int a, int b, int c) {
long setA = num / a, setB = num / b, setC = num / c;
long setAB = num / lcm(a, b);
long setAC = num / lcm(a, c);
long setBC = num / lcm(b, c);
long setABC = num / lcm(lcm(a, b), c);
// set theory theorem: A + B + C - A ∩ B - A ∩ C - B ∩ C + A ∩ B ∩ C
return setA + setB + setC - setAB - setAC - setBC + setABC;
}
}
```

```
class Solution {
public:
int nthUglyNumber(int n, int a, int b, int c) {
// the problem statement says the result is within the range [1, 2 * 10^9],
// so we initialize the search range with both ends closed according to this range
int left = 1, right = 2e9;
// binary search for the left boundary
while (left <= right) {
int mid = left + (right - left) / 2;
if (f(mid, a, b, c) < n) {
// the number of elements that meet the condition in [1..mid] is less than n, so the target is on the right half
left = mid + 1;
} else {
// the number of elements that meet the condition in [1..mid] is greater than n, so the target is on the left half
right = mid - 1;
}
}
return left;
}
// calculate the greatest common divisor (Euclidean algorithm)
long gcd(long a, long b) {
if (a < b) {
// ensure a > b
return gcd(b, a);
}
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
// least common multiple
long lcm(long a, long b) {
// the least common multiple is the product divided by the greatest common divisor
return a * b / gcd(a, b);
}
// calculate how many numbers between [1..num] can be divided by a or b or c
long f(int num, int a, int b, int c) {
long setA = num / a, setB = num / b, setC = num / c;
long setAB = num / lcm(a, b);
long setAC = num / lcm(a, c);
long setBC = num / lcm(b, c);
long setABC = num / lcm(lcm(a, b), c);
// set theory theorem: A + B + C - A ∩ B - A ∩ C - B ∩ C + A ∩ B ∩ C
return setA + setB + setC - setAB - setAC - setBC + setABC;
}
};
```

```
class Solution:
def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
# The problem states that the result is within the range [1, 2 * 10^9],
# so initialize the search range with both ends closed according to this range
left, right = 1, int(2e9)
# Binary search for the left boundary
while left <= right:
mid = left + (right - left) // 2
if self.f(mid, a, b, c) < n:
# The number of elements meeting the condition in [1..mid] is less than n, so the target is on the right half
left = mid + 1
else:
# The number of elements meeting the condition in [1..mid] is greater than n, so the target is on the left half
right = mid - 1
return left
# Calculate the greatest common divisor (Euclidean algorithm)
def gcd(self, a: int, b: int) -> int:
if a < b:
# Ensure a > b
return self.gcd(b, a)
if b == 0:
return a
return self.gcd(b, a % b)
# Least common multiple
def lcm(self, a: int, b: int) -> int:
# The least common multiple is the product divided by the greatest common divisor
return a * b // self.gcd(a, b)
# Calculate how many numbers between [1..num] can be divided by a or b or c
def f(self, num: int, a: int, b: int, c: int) -> int:
setA, setB, setC = num // a, num // b, num // c
setAB = num // self.lcm(a, b)
setAC = num // self.lcm(a, c)
setBC = num // self.lcm(b, c)
setABC = num // self.lcm(self.lcm(a, b), c)
# Set theory theorem: A + B + C - A ∩ B - A ∩ C - B ∩ C + A ∩ B ∩ C
return setA + setB + setC - setAB - setAC - setBC + setABC
```

```
func nthUglyNumber(n int, a int, b int, c int) int {
// the problem states that the result is within the range [1, 2 * 10^9],
// so initialize the search range with both ends closed according to this range
left, right := 1, int(2e9)
// binary search for the left boundary
for left <= right {
mid := left + (right - left) / 2
if f(mid, a, b, c) < n {
// the number of elements meeting the condition in [1..mid] is less than n, so the target is in the right half
left = mid + 1
} else {
// the number of elements meeting the condition in [1..mid] is greater than n, so the target is in the left half
right = mid - 1
}
}
return left
}
// calculate the greatest common divisor (Euclidean algorithm)
func gcd(a, b int) int {
if a < b {
// ensure a > b
return gcd(b, a)
}
if b == 0 {
return a
}
return gcd(b, a % b)
}
// least common multiple
func lcm(a, b int) int {
// the least common multiple is the product divided by the greatest common divisor
return a * b / gcd(a, b)
}
// calculate how many numbers between [1..num] can be divided by a or b or c
func f(num, a, b, c int) int {
setA, setB, setC := num / a, num / b, num / c
setAB := num / lcm(a, b)
setAC := num / lcm(a, c)
setBC := num / lcm(b, c)
setABC := num / lcm(lcm(a, b), c)
// set theory theorem: A + B + C - A ∩ B - A ∩ C - B ∩ C + A ∩ B ∩ C
return setA + setB + setC - setAB - setAC - setBC + setABC
}
```

```
var nthUglyNumber = function(n, a, b, c) {
// the problem statement says the result is within the range [1, 2 * 10^9],
// so initialize the search range with both ends closed according to this range
let left = 1, right = 2 * 10 ** 9;
// binary search for the left boundary
while (left <= right) {
let mid = left + Math.floor((right - left) / 2);
if (f(mid, a, b, c) < n) {
// the number of elements meeting the condition in [1..mid] is less than n, so the target is on the right half
left = mid + 1;
} else {
// the number of elements meeting the condition in [1..mid] is greater than n, so the target is on the left half
right = mid - 1;
}
}
return left;
};
// calculate the greatest common divisor (Euclidean algorithm)
var gcd = function(a, b) {
if (a < b) {
// ensure a > b
return gcd(b, a);
}
if (b === 0) {
return a;
}
return gcd(b, a % b);
};
// least common multiple
var lcm = function(a, b) {
// the least common multiple is the product divided by the greatest common divisor
return a * b / gcd(a, b);
};
// calculate how many numbers between [1..num] can be divided by a or b or c
var f = function(num, a, b, c) {
let setA = Math.floor(num / a), setB = Math.floor(num / b), setC = Math.floor(num / c);
let setAB = Math.floor(num / lcm(a, b));
let setAC = Math.floor(num / lcm(a, c));
let setBC = Math.floor(num / lcm(b, c));
let setABC = Math.floor(num / lcm(lcm(a, b), c));
// set theory theorem: A + B + C - A ∩ B - A ∩ C - B ∩ C + A ∩ B ∩ C
return setA + setB + setC - setAB - setAC - setBC + setABC;
};
```

By implementing the `f`

function and combining it with the previous binary search template, the time complexity is reduced to logarithmic level, allowing for an efficient solution to this problem.

This concludes all the problems related to "ugly numbers," which involve knowledge points such as the fundamental theorem of arithmetic, merging multiple sorted linked lists, binary search templates, the Euclidean algorithm, and more. If you haven't encountered similar problems before, it might be challenging to come up with solutions. However, once you've practiced them, solving these problems becomes straightforward. Therefore, I consider these mathematical problems to be of the type that are easy for those who know and hard for those who don't.

For more mathematical algorithms, see How to Efficiently Find Prime Numbers, Discussing Random Algorithms in Games, Common Bit Manipulations, and Algorithm Problems Solvable with a Single Line of Code.