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 <= 1091 <= 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)
}
};
Input
n = 3, a = 2, b = 3, c = 5
Output
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
Input
n = 3, a = 2, b = 3, c = 5
Output
4