Ugly Number III - Solution & Explanation
Problem Statement
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].
Approach Overview
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.
Approach 1: Binary Search with Inclusion-Exclusion Principle
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:
- Multiples of `a`: `x/a`
- Multiples of `b`: `x/b`
- Multiples of `c`: `x/c`
- Subtract the over-counted multiples of lcm(a, b), lcm(b, c), lcm(a, c)
- Add back the multiples of lcm(a, b, c) as they are subtracted out too many times.
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.
Complexity
Time Complexity: O(log(max_range)) where max_range is 2e9.
Space Complexity: O(1).
Approach 2: Priority Queue (Min-Heap) Simulation
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.
Code
Python
Complexity
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 3: 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 \frac{x}{a} \right\rfloor numbers divisible by a, \left\lfloor \frac{x}{b} \right\rfloor numbers divisible by b, \left\lfloor \frac{x}{c} \right\rfloor numbers divisible by c, \left\lfloor \frac{x}{lcm(a, b)} \right\rfloor numbers divisible by both a and b, \left\lfloor \frac{x}{lcm(a, c)} \right\rfloor numbers divisible by both a and c, \left\lfloor \frac{x}{lcm(b, c)} \right\rfloor numbers divisible by both b and c, and \left\lfloor \frac{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 \frac{x}{a} \right\rfloor + \left\lfloor \frac{x}{b} \right\rfloor + \left\lfloor \frac{x}{c} \right\rfloor - \left\lfloor \frac{x}{lcm(a, b)} \right\rfloor - \left\lfloor \frac{x}{lcm(a, c)} \right\rfloor - \left\lfloor \frac{x}{lcm(b, c)} \right\rfloor + \left\lfloor \frac{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 times 10^9, where 2 times 10^9 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 times 10^9. The space complexity is O(1)$.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| 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. |
| Binary Search + Inclusion-Exclusion Principle | — |
Detailed Complexity Analysis
| 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 |
Video Solution
1201 Ugly Number III • Kelvin Chandra • 7,504 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Ugly Number III easy or hard?
How to solve Ugly Number III in O(log n)?
What is the best approach for Ugly Number III?
Is Ugly Number III asked at Google/Amazon/Meta?
What data structure is used in Ugly Number III?
What is the time complexity of Ugly Number III?
Ugly Number III Python or Java solution approach?
Ready to solve this problem?
Practice Ugly Number III with our built-in code editor and test cases.
Practice on FleetCode