Formatted question description: https://leetcode.ca/all/1201.html

# 1201. Ugly Number III

## Level

Medium

## Description

Write a program to find the `n`

-th ugly number.

Ugly numbers are **positive integers** which are divisible by `a`

**or** `b`

**or** `c`

.

**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.

**Example 4:**

**Input:** n = 1000000000, a = 2, b = 217983653, c = 336916467

**Output:** 1999999984

**Constraints:**

`1 <= n, a, b, c <= 10^9`

`1 <= a * b * c <= 10^18`

- It’s guaranteed that the result will be in range
`[1, 2 * 10^9]`

## Solution

Use binary search. Initially set `low`

to be 1 and `high`

to be 2 * 10^9. The condition of binary search is `low < high`

. Each time set `mid`

to be the average of `low`

and `high`

, and calculate the number of ugly numbers that are less than or equal to `mid`

, which can be calculated using inclusion-exclusion principle. If the number of ugly numbers is less than `n`

, then obviously the `n`

-th ugly number is greater than `mid`

, so set `low = mid + 1`

. Otherwise, the `n`

-th ugly number may be `mid`

or less than `mid`

, so set `high = mid`

. After the search ends, return `low`

.

```
class Solution {
public int nthUglyNumber(int n, int a, int b, int c) {
long lcmAB = a / gcd(a, b) * b;
long lcmBC = b / gcd(b, c) * c;
long lcmAC = a / gcd(a, c) * c;
long lcmABC = lcmAB / gcd(lcmAB, c) * c;
long low = 1, high = 2000000000;
while (low < high) {
long mid = (high - low) / 2 + low;
long count = mid / a + mid / b + mid / c - mid / lcmAB - mid / lcmBC - mid / lcmAC + mid / lcmABC;
if (count < n)
low = mid + 1;
else
high = mid;
}
return (int) low;
}
public long gcd(long a, long b) {
if (a == 0 && b == 0)
return 1;
while (a != 0 && b != 0) {
if (a > b) {
long temp = a;
a = b;
b = temp;
}
b %= a;
}
return a == 0 ? b : a;
}
}
```