In this guide, you will get 1201. Ugly Number III LeetCode Solution with the best time and space complexity. The solution to Ugly Number III problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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].
Complexity Analysis
Time Complexity:
Space Complexity:
1201. Ugly Number III LeetCode Solution in C++
class Solution {
public:
int nthUglyNumber(int n, long a, long b, long c) {
const long ab = a * b / __gcd(a, b);
const long ac = a * c / __gcd(a, c);
const long bc = b * c / __gcd(b, c);
const long abc = a * bc / __gcd(a, bc);
int l = 1;
int r = 2'000'000'000;
while (l < r) {
const int m = l + (r - l) / 2;
if (m / a + m / b + m / c - m / ab - m / ac - m / bc + m / abc >= n)
r = m;
else
l = m + 1;
}
return l;
}
}; /* code provided by PROGIEZ */
1201. Ugly Number III LeetCode Solution in Java
class Solution {
public int nthUglyNumber(int n, long a, long b, long c) {
final long ab = a * b / gcd(a, b);
final long ac = a * c / gcd(a, c);
final long bc = b * c / gcd(b, c);
final long abc = a * bc / gcd(a, bc);
int l = 1;
int r = 2_000_000_000;
while (l < r) {
final int m = (l + r) / 2;
if (m / a + m / b + m / c - m / ab - m / ac - m / bc + m / abc >= n)
r = m;
else
l = m + 1;
}
return l;
}
private long gcd(long a, long b) {
return b == 0 ? a : gcd(b, a % b);
}
} // code provided by PROGIEZ
1201. Ugly Number III LeetCode Solution in Python
class Solution:
def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
ab = a * b // math.gcd(a, b)
ac = a * c // math.gcd(a, c)
bc = b * c // math.gcd(b, c)
abc = a * bc // math.gcd(a, bc)
return bisect.bisect_left(range(2 * 10**9), n,
key=lambda m: m // a + m // b + m // c
- m // ab - m // ac - m // bc
+ m // abc) # code by PROGIEZ
