Prompt: 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:
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.
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.
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.
Input: n = 1000000000, a = 2, b = 217983653, c = 336916467
Output: 1999999984
Solution: We can do a binary search to find the nth ugly number within the range of 1 to 2 * 109. We can find the number of multiples in a certain number by using the before code snippet:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def lcm(x, y):
return x * y // gcd(x,y)
def total_num_of_multiples(number):
ab = lcm(a,b)
bc = lcm(b,c)
ac = lcm(a,c)
abc = lcm(a, bc)
result = number // a + number // b + number // c
result -= number // ab + number // bc + number // ac
result += number // abc
return result
The runtime for this solution is O(log n).