##### Welcome to Subscribe On Youtube

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

# 1201. Ugly Number III

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;
}
}

• // OJ: https://leetcode.com/problems/ugly-number-iii/
// Time: O(logN)
// Space: O(1)
class Solution {
long lcm(long a, long b) { // least common multiple
return a * b / gcd(a, b);
}
public:
int nthUglyNumber(int n, int a, int b, int c) {
long L = 1, R = 2e9;
auto le = [&](long M) {
return M / a + M / b + M / c - M / lcm(a, b) - M / lcm(b, c) - M / lcm(a, c) + M / lcm(lcm(a, b), c);
};
while (L <= R) {
long M = (L + R) / 2, cnt = le(M);
if (cnt < n) L = M + 1;
else R = M - 1;
}
return L;
}
};

• class Solution:
def f(self, num: int, a: int, b: int, c: int) -> int:
return (
num // a
+ num // b
+ num // c
- num // math.lcm(a, b)
- num // math.lcm(a, c)
- num // math.lcm(b, c)
+ num // math.lcm(a, b, c)
)

def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
left, right = 1, int(2e9)
while left <= right:
mid = left + (right - left) // 2
if self.f(mid, a, b, c) < n:
left = mid + 1
else:
right = mid - 1
return left

############

# 1201. Ugly Number III
# https://leetcode.com/problems/ugly-number-iii

class Solution:
def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:

def enough(x):
total = (x // a) + (x // b) + (x // c) - (x // ab) - (x // bc) - (x // ac) + (x // abc)

ab = a*b // math.gcd(a,b)
bc = b*c // math.gcd(b,c)
ac = a*c // math.gcd(a,c)
abc = a*bc // math.gcd(a,bc)

left, right = 1, 10 ** 10
while left < right:
mid = left + (right-left) // 2

if enough(mid):
right = mid
else:
left = mid + 1

return left


• func nthUglyNumber(n int, a int, b int, c int) int {
left, right := 1, int(2e9)
for left <= right {
mid := left + (right-left)/2
if f(mid, a, b, c) < n {
left = mid + 1
} else {
right = mid - 1
}
}
return left
}

func f(num int, a int, b int, c int) int {
return num/a + num/b + num/c - num/lcm(a, b) - num/lcm(a, c) - num/lcm(b, c) + num/lcm(lcm(a, b), c)
}

// Least common multiple
func lcm(a, b int) int {
// Greatest common divisor
gcd := func(x, y int) int {
for y != 0 {
if x < y {
x, y = y, x
}
x, y = y, x%y
}
return x
}
return a * b / gcd(a, b)
}