# Ugly Number III
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/ugly-number-iii)
Canonical: https://scaleengineer.com/dsa/problems/ugly-number-iii
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Companies:** [American Express](https://scaleengineer.com/companies/american-express)
---
## Problem
An **ugly number** is a positive integer that is divisible by `a`, `b`, or `c`.

Given four integers `n`, `a`, `b`, and `c`, return the `nth` **ugly number**.

**Example 1:**

**Input:** n = 3, a = 2, b = 3, c = 5
**Output:** 4
**Explanation:** The ugly numbers are 2, 3, 4, 5, 6, 8, 9, 10... The 3rd is 4.

**Example 2:**

**Input:** n = 4, a = 2, b = 3, c = 4
**Output:** 6
**Explanation:** The ugly numbers are 2, 3, 4, 6, 8, 9, 10, 12... The 4th is 6.

**Example 3:**

**Input:** n = 5, a = 2, b = 11, c = 13
**Output:** 10
**Explanation:** The ugly numbers are 2, 4, 6, 8, 10, 11, 12, 13... The 5th is 10.

**Constraints:**

* `1 <= n, a, b, c <= 109`
* `1 <= a * b * c <= 1018`
* It is guaranteed that the result will be in range `[1, 2 * 109]`.

# Approaches
## Brute Force Simulation
This approach involves a straightforward simulation. We iterate through positive integers starting from 1, and for each number, we check if it's divisible by `a`, `b`, or `c`. We maintain a counter for the ugly numbers found. When the counter reaches `n`, the current integer is our answer.
**Time:** O(K), where K is the value of the n-th ugly number. In the worst case, K can be up to 2 * 10^9, making this approach infeasible. · **Space:** O(1) as we only use a few variables to store the count and the current number.
**Pros:** Simple to understand and implement.
**Cons:** Extremely inefficient and will result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
The algorithm works by iterating through numbers one by one and checking if they meet the criteria of an ugly number. It's the most intuitive way to think about the problem but fails to scale.

```java
class Solution {
    public int nthUglyNumber(int n, int a, int b, int c) {
        int count = 0;
        int num = 0;
        while (count < n) {
            num++;
            if (num % a == 0 || num % b == 0 || num % c == 0) {
                count++;
            }
        }
        return num;
    }
}
```

This method is easy to understand but is too slow for the given constraints, as the n-th ugly number can be as large as 2 * 10^9, leading to a very high number of iterations.
### Algorithm
- Initialize a counter `count` to 0 and the current number `num` to 0.
- Enter a loop that continues until `count` equals `n`.
- Inside the loop, increment `num`.
- Check if `num` is divisible by `a`, `b`, or `c` (i.e., `num % a == 0 || num % b == 0 || num % c == 0`).
- If it is, increment the `count`.
- Once the loop terminates (when `count == n`), `num` holds the value of the n-th ugly number.

## Binary Search with Inclusion-Exclusion Principle
A much more efficient approach is to use binary search on the answer. The sequence of ugly numbers is monotonically increasing. This allows us to search for the n-th ugly number within a specific range, which is `[1, 2 * 10^9]` according to the problem constraints. For any given number `x`, we need an efficient way to determine how many ugly numbers are less than or equal to `x`. If we can do this, we can use binary search to find the smallest `x` for which this count is at least `n`.
**Time:** O(log(M)), where M is the upper bound of the search space (2 * 10^9). The GCD calculation takes logarithmic time relative to its inputs, but this is a very small factor. The overall complexity is dominated by the binary search. · **Space:** O(1) as we only store a few variables for the binary search and LCM values.
**Pros:** Highly efficient and can handle the large constraints.; Optimal solution for this problem type.
**Cons:** More complex to conceptualize and implement correctly.; Requires knowledge of the Inclusion-Exclusion principle and number theory concepts like GCD and LCM.; Care must be taken to handle potential integer overflows during LCM calculations.
### Explanation
To find the number of ugly numbers less than or equal to a given value `x`, we use the **Principle of Inclusion-Exclusion**.

Let `count(k)` be the number of positive integers less than or equal to `x` that are divisible by `k`. This is simply `x / k` using integer division.

The total number of ugly numbers up to `x` is the size of the union of three sets: multiples of `a`, multiples of `b`, and multiples of `c`.

The formula is:
`count(x) = (x/a) + (x/b) + (x/c) - (x/lcm(a,b)) - (x/lcm(a,c)) - (x/lcm(b,c)) + (x/lcm(a,b,c))`

Here, `lcm(p, q)` is the least common multiple of `p` and `q`. It can be calculated using the greatest common divisor (GCD) as `lcm(p, q) = (p * q) / gcd(p, q)`. To avoid potential integer overflow, it's safer to compute it as `(p / gcd(p, q)) * q`. All these calculations must be done using 64-bit integers (`long` in Java) to handle large numbers.

```java
class Solution {
    public int nthUglyNumber(int n, int a, int b, int c) {
        int low = 1, high = 2 * (int) 1e9;
        int ans = 0;

        long ab = lcm((long)a, (long)b);
        long ac = lcm((long)a, (long)c);
        long bc = lcm((long)b, (long)c);
        long abc = lcm((long)a, bc);

        while (low <= high) {
            int mid = low + (high - low) / 2;
            long count = mid / (long)a + mid / (long)b + mid / (long)c
                       - mid / ab - mid / ac - mid / bc
                       + mid / abc;

            if (count >= n) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }

    private long gcd(long x, long y) {
        if (x == 0) {
            return y;
        }
        return gcd(y % x, x);
    }

    private long lcm(long x, long y) {
        if (x == 0 || y == 0) {
            return 0;
        }
        // To avoid overflow, compute as (x / gcd(x, y)) * y
        // The result can be larger than the max answer, which is fine.
        // The problem constraints ensure lcm(a,b,c) fits in a long.
        return (x / gcd(x, y)) * y;
    }
}
```
### Algorithm
1.  Set the search range `low = 1` and `high = 2 * 10^9`.
2.  Pre-calculate the required LCM values using 64-bit integers: `lcm(a,b)`, `lcm(a,c)`, `lcm(b,c)`, and `lcm(a,b,c)`.
3.  While `low <= high`:
    -   Calculate `mid = low + (high - low) / 2`.
    -   Use the Inclusion-Exclusion formula to find the `count` of ugly numbers up to `mid`.
    -   If `count >= n`, it means `mid` could be our answer, but there might be a smaller valid answer. So, we store `mid` as a potential answer and shrink the search space to the lower half: `ans = mid`, `high = mid - 1`.
    -   If `count < n`, `mid` is too small. We need to search in the upper half: `low = mid + 1`.
4.  Return the final stored answer `ans`.

# Solutions
### Java

```java
class Solution { public int nthUglyNumber ( int n , int a , int b , int c ) { long ab = lcm ( a , b ); long bc = lcm ( b , c ); long ac = lcm ( a , c ); long abc = lcm ( ab , c ); long l = 1 , r = 2000000000 ; while ( l < r ) { long mid = ( l + r ) >> 1 ; if ( mid / a + mid / b + mid / c - mid / ab - mid / bc - mid / ac + mid / abc >= n ) { r = mid ; } else { l = mid + 1 ; } } return ( int ) l ; } private long gcd ( long a , long b ) { return b == 0 ? a : gcd ( b , a % b ); } private long lcm ( long a , long b ) { return a * b / gcd ( a , b ); } }
```

### CPP

```cpp
class Solution { public: int nthUglyNumber ( int n , int a , int b , int c ) { long long ab = lcm ( a , b ); long long bc = lcm ( b , c ); long long ac = lcm ( a , c ); long long abc = lcm ( ab , c ); long long l = 1 , r = 2000000000 ; while ( l < r ) { long long mid = ( l + r ) >> 1 ; if ( mid / a + mid / b + mid / c - mid / ab - mid / bc - mid / ac + mid / abc >= n ) { r = mid ; } else { l = mid + 1 ; } } return l ; } long long lcm ( long long a , long long b ) { return a * b / gcd ( a , b ); } long long gcd ( long long a , long long b ) { return b == 0 ? a : gcd ( b , a % b ); } };
```

### Python

```python
class Solution : def nthUglyNumber ( self , n : int , a : int , b : int , c : int ) -> int : ab = lcm ( a , b ) bc = lcm ( b , c ) ac = lcm ( a , c ) abc = lcm ( a , b , c ) l , r = 1 , 2 * 10 ** 9 while l < r : mid = ( l + r ) >> 1 if ( mid // a + mid // b + mid // c - mid // ab - mid // bc - mid // ac + mid // abc >= n ): r = mid else : l = mid + 1 return l
```