Welcome to Subscribe On Youtube
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; } }
-
// 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) return total >= n 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) }
-
function nthUglyNumber(n: number, a: number, b: number, c: number): number { const ab = lcm(BigInt(a), BigInt(b)); const bc = lcm(BigInt(b), BigInt(c)); const ac = lcm(BigInt(a), BigInt(c)); const abc = lcm(BigInt(a), bc); let l = 1n; let r = BigInt(2e9); while (l < r) { const mid = (l + r) >> 1n; const count = mid / BigInt(a) + mid / BigInt(b) + mid / BigInt(c) - mid / ab - mid / bc - mid / ac + mid / abc; if (count >= BigInt(n)) { r = mid; } else { l = mid + 1n; } } return Number(l); } function gcd(a: bigint, b: bigint): bigint { return b === 0n ? a : gcd(b, a % b); } function lcm(a: bigint, b: bigint): bigint { return (a * b) / gcd(a, b); }