LeetCode 1201. Ugly Number III Solution in Java, C++, Python & More | Explanation + Code

Description

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 <= 109
• 1 <= a * b * c <= 1018
• It is guaranteed that the result will be in range [1, 2 * 109].

Solutions

Solution 1: Binary Search + Inclusion-Exclusion Principle

We can transform the problem into: find the smallest positive integer x such that the number of ugly numbers less than or equal to x is exactly n.

For a positive integer x, there are \left\lfloor ^x⁄_a \right\rfloor numbers divisible by a, \left\lfloor ^x⁄_b \right\rfloor numbers divisible by b, \left\lfloor ^x⁄_c \right\rfloor numbers divisible by c, \left\lfloor ^x⁄_{lcm(a, b)} \right\rfloor numbers divisible by both a and b, \left\lfloor ^x⁄_{lcm(a, c)} \right\rfloor numbers divisible by both a and c, \left\lfloor ^x⁄_{lcm(b, c)} \right\rfloor numbers divisible by both b and c, and \left\lfloor ^x⁄_{lcm(a, b, c)} \right\rfloor numbers divisible by a, b, and c at the same time. According to the inclusion-exclusion principle, the number of ugly numbers less than or equal to x is:

\left\lfloor ^x⁄_a \right\rfloor + \left\lfloor ^x⁄_b \right\rfloor + \left\lfloor ^x⁄_c \right\rfloor - \left\lfloor ^x⁄_{lcm(a, b)} \right\rfloor - \left\lfloor ^x⁄_{lcm(a, c)} \right\rfloor - \left\lfloor ^x⁄_{lcm(b, c)} \right\rfloor + \left\lfloor ^x⁄_{lcm(a, b, c)} \right\rfloor

We can use binary search to find the smallest positive integer x such that the number of ugly numbers less than or equal to x is exactly n.

Define the left boundary of binary search as l=1 and the right boundary as r=2 × 10⁹, where 2 × 10⁹ is the maximum value given by the problem. In each step of binary search, we find the middle number mid. If the number of ugly numbers less than or equal to mid is greater than or equal to n, it means that the smallest positive integer x falls in the interval [l,mid], otherwise it falls in the interval [mid+1,r]. During the binary search process, we need to continuously update the number of ugly numbers less than or equal to mid until we find the smallest positive integer x.

The time complexity is O(log m), where m = 2 × 10⁹. The space complexity is O(1).

PythonJavaC++GoTypeScript

class Solution: def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int: ab = lcm(a, b) bc = lcm(b, c) ac = lcm(a, c) abc = lcm(a, b, c) l, r = 1, 2 * 10**9 while l < r: mid = (l + r) >> 1 if ( mid // a + mid // b + mid // c - mid // ab - mid // bc - mid // ac + mid // abc >= n ): r = mid else: l = mid + 1 return l(code-box)

class Solution { public int nthUglyNumber(int n, int a, int b, int c) { long ab = lcm(a, b); long bc = lcm(b, c); long ac = lcm(a, c); long abc = lcm(ab, c); long l = 1, r = 2000000000; while (l < r) { long mid = (l + r) >> 1; if (mid / a + mid / b + mid / c - mid / ab - mid / bc - mid / ac + mid / abc >= n) { r = mid; } else { l = mid + 1; } } return (int) l; } private long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); } private long lcm(long a, long b) { return a * b / gcd(a, b); } }(code-box)

class Solution { public: int nthUglyNumber(int n, int a, int b, int c) { long long ab = lcm(a, b); long long bc = lcm(b, c); long long ac = lcm(a, c); long long abc = lcm(ab, c); long long l = 1, r = 2000000000; while (l < r) { long long mid = (l + r) >> 1; if (mid / a + mid / b + mid / c - mid / ab - mid / bc - mid / ac + mid / abc >= n) { r = mid; } else { l = mid + 1; } } return l; } long long lcm(long long a, long long b) { return a * b / gcd(a, b); } long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); } };(code-box)

func nthUglyNumber(n int, a int, b int, c int) int { ab, bc, ac := lcm(a, b), lcm(b, c), lcm(a, c) abc := lcm(ab, c) var l, r int = 1, 2e9 for l < r { mid := (l + r) >> 1 if mid/a+mid/b+mid/c-mid/ab-mid/bc-mid/ac+mid/abc >= n { r = mid } else { l = mid + 1 } } return l } func gcd(a, b int) int { if b == 0 { return a } return gcd(b, a%b) } func lcm(a, b int) int { return a * b / gcd(a, b) }(code-box)

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); }(code-box)