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[1, 2 * 109].Problem Overview: You need to find the nth positive integer that is divisible by at least one of three numbers a, b, or c. These are called ugly numbers for this problem. The challenge is that n can be as large as 10^9, so generating numbers one by one is not feasible.
Approach 1: Priority Queue (Min-Heap) Simulation (Time: O(n log k), Space: O(n))
This method simulates the generation of ugly numbers using a min-heap. Start by pushing a, b, and c into the heap and repeatedly extract the smallest value while pushing the next multiples. A set or duplicate-check is required because many numbers appear through multiple paths (for example, 6 from both 2×3 and 3×2). The heap always keeps the smallest candidate on top, so extracting the minimum n times yields the answer. This approach demonstrates the idea clearly but becomes slow when n is large.
Approach 2: Binary Search with Inclusion-Exclusion Principle (Time: O(log R), Space: O(1))
The optimal solution uses binary search combined with the inclusion-exclusion principle from math and number theory. Instead of generating ugly numbers, search for the smallest integer x such that at least n numbers ≤ x are divisible by a, b, or c.
To count how many valid numbers are ≤ x, compute:
count = x/a + x/b + x/c - x/lcm(a,b) - x/lcm(a,c) - x/lcm(b,c) + x/lcm(a,b,c)
This formula avoids double-counting numbers divisible by multiple values. The lcm values are derived using lcm(a,b) = a * b / gcd(a,b). During binary search, if the count is at least n, move the right boundary left; otherwise move the left boundary right. The search space ranges up to about 2 × 10^9, so the algorithm runs in roughly O(log R) iterations with constant work per step.
Recommended for interviews: Interviewers expect the binary search + inclusion-exclusion solution. The heap simulation shows you understand how ugly numbers could be generated, but it does not scale to the constraints. The optimal approach demonstrates strong understanding of counting techniques, LCM/GCD math, and binary search on the answer, which are common patterns in medium-to-hard algorithm problems.
This approach uses binary search to efficiently find the nth ugly number. The idea is to use binary search over the possible range of numbers to determine the first number that has at least n multiples of a, b, or c.
To calculate the number of multiples of `a`, `b`, or `c` less than or equal to some number `x`, we use the inclusion-exclusion principle:
This solution iteratively searches for the nth ugly number by leveraging the binary search on the number range up to 2e9. It calculates the count of numbers up to 'mid' divisible by any of a, b, or c using the inclusion-exclusion principle.
Time Complexity: O(log(max_range)) where max_range is 2e9.
Space Complexity: O(1).
This approach simulates the generation of ugly numbers using a priority queue (or min-heap). We start with the smallest numbers (a, b, c) and generate subsequent numbers by multiplying these with a, b, c, maintaining a set to avoid duplicates. The nth element extracted from the heap will be the nth ugly number.
This approach uses a min-heap to track and expand the smallest ugly number each iteration. For each current smallest, multiply by a, b, and c to generate new numbers, ensuring unique numbers with a set to prevent duplicates.
Python
Time Complexity: O(n log n), given the heap operations.
Space Complexity: O(n), since we're storing all the unique ugly numbers until the nth one.
| Approach | Complexity |
|---|---|
| Binary Search with Inclusion-Exclusion Principle | Time Complexity: O(log(max_range)) where max_range is 2e9. |
| Priority Queue (Min-Heap) Simulation | Time Complexity: O(n log n), given the heap operations. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Priority Queue (Min-Heap) Simulation | O(n log k) | O(n) | Useful for understanding how ugly numbers can be generated sequentially; works for small n |
| Binary Search with Inclusion-Exclusion | O(log R) | O(1) | Best approach for large constraints; standard interview solution |
1201 Ugly Number III • Kelvin Chandra • 7,350 views views
Watch 9 more video solutions →Practice Ugly Number III with our built-in code editor and test cases.
Practice on FleetCode