## Algorithm

Problem Name: 1201. Ugly Number III

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]`.

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const nthUglyNumber = function(n, a, b, c) {
let lo = 1, hi = 2 * 1e9;
const { floor: f } = Math
let ab = a * b / gcd(a, b);
let bc = b * c / gcd(b, c);
let ac = a * c / gcd(a, c);
let abc = a * bc / gcd(a, bc);
while(lo  <  hi) {
let mid = lo + Math.floor((hi - lo) / 2);
if(valid(mid)) hi = mid;
else lo = mid + 1;
}
return lo;

function valid(mid) {
let res = f(mid / a) + f(mid / b) + f(mid / c) - f(mid / ab) - f(mid / bc) - f(mid / ac) + f(mid / abc)
return res >= n
}

function gcd(a, b) {
return b === 0 ? a : gcd(b, a % b)
}
};
``````
Copy The Code &

Input

cmd
n = 3, a = 2, b = 3, c = 5

Output

cmd
4

### #2 Code Example with Python Programming

```Code - Python Programming```

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

``````
Copy The Code &

Input

cmd
n = 3, a = 2, b = 3, c = 5

Output

cmd
4