LeetCode 1201 - Ugly Number III
The problem defines an "ugly number" as any positive integer that is divisible by at least one of the three given integers a, b, or c.
Difficulty: 🟡 Medium
Topics: Math, Binary Search, Combinatorics, Number Theory
Solution
Problem Understanding
The problem defines an "ugly number" as any positive integer that is divisible by at least one of the three given integers a, b, or c.
We are given four integers:
n, representing which ugly number we want to finda,b, andc, representing the divisibility conditions
The task is to return the nth positive integer that is divisible by a, b, or c.
For example, if a = 2, b = 3, and c = 5, then the ugly numbers are:
2, 3, 4, 5, 6, 8, 9, 10, ...
The third ugly number is 4.
The important detail is that a number only needs to be divisible by one of the values. If a number is divisible by multiple values, it still counts only once. For example, 6 is divisible by both 2 and 3, but it is counted as a single ugly number.
The constraints are extremely important:
n,a,b, andccan each be as large as10^9a * b * ccan be as large as10^18
These limits immediately tell us that generating ugly numbers one by one is not feasible. Even iterating through all integers up to the answer would be too slow in the worst case.
The problem also guarantees that the final answer fits within the range [1, 2 * 10^9]. This gives us a safe upper bound for binary search.
Several edge cases matter here:
- Some divisors may overlap heavily, such as
a = 2,b = 4,c = 8 - Two or all three divisors may be equal
- Large values can cause overflow when computing least common multiples
- Numbers divisible by multiple divisors must not be double-counted
The main challenge is efficiently counting how many ugly numbers exist less than or equal to some value x.
Approaches
Brute Force Approach
A straightforward solution is to iterate through positive integers starting from 1 and count how many numbers are divisible by a, b, or c.
For each integer:
- Check whether it is divisible by
a - Or divisible by
b - Or divisible by
c
If any condition is true, increment the ugly number count.
Once the count reaches n, return the current number.
This approach is correct because it directly simulates the definition of ugly numbers. However, it is far too slow for the given constraints. If the answer is near 2 * 10^9, iterating through billions of integers is infeasible.
Optimal Approach
The key observation is that we do not need to generate ugly numbers explicitly.
Instead, we can answer the question:
"How many ugly numbers are less than or equal to
x?"
If we can compute this efficiently, then we can binary search for the smallest x such that there are at least n ugly numbers less than or equal to x.
To count ugly numbers up to x, we use the Inclusion-Exclusion Principle.
The count of numbers divisible by:
aisx // abisx // bcisx // c
But numbers divisible by both a and b are counted twice, so we subtract:
x // lcm(a, b)x // lcm(a, c)x // lcm(b, c)
Then numbers divisible by all three were subtracted too many times, so we add back:
x // lcm(a, b, c)
The formula becomes:
$count(x)=\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}{\mathrm{lcm}(a,b)}\right\rfloor-\left\lfloor\frac{x}{\mathrm{lcm}(a,c)}\right\rfloor-\left\lfloor\frac{x}{\mathrm{lcm}(b,c)}\right\rfloor+\left\lfloor\frac{x}{\mathrm{lcm}(a,b,c)}\right\rfloor$
This counting function is monotonic. As x increases, the number of ugly numbers less than or equal to x never decreases. That makes binary search applicable.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(answer) | O(1) | Iterates through every integer until the nth ugly number |
| Optimal | O(log(2 × 10^9)) | O(1) | Uses binary search with inclusion-exclusion counting |
Algorithm Walkthrough
- Compute the least common multiples needed for inclusion-exclusion.
We need:
lcm(a, b)lcm(a, c)lcm(b, c)lcm(a, b, c)
These values help us count overlaps correctly. 2. Define a counting function.
For a given number x, calculate how many integers from 1 to x are divisible by at least one of a, b, or c.
The Inclusion-Exclusion Principle ensures numbers are counted exactly once. 3. Initialize binary search boundaries.
The smallest possible answer is 1.
The largest possible answer is guaranteed to be at most 2 * 10^9, so we use that as the upper bound.
4. Perform binary search.
At each iteration:
- Compute
mid - Count how many ugly numbers are
<= mid
If the count is at least n, then the answer could be mid or smaller, so move the right boundary left.
Otherwise, there are not enough ugly numbers yet, so move the left boundary right. 5. Continue until the search converges.
Binary search stops when left == right.
That value is the smallest integer containing at least n ugly numbers, which means it is exactly the nth ugly number.
Why it works
The counting function is monotonic. If x1 < x2, then the number of ugly numbers up to x1 cannot exceed the number up to x2.
Binary search works on monotonic functions because we can eliminate half the search space at every step.
The Inclusion-Exclusion Principle guarantees that each valid number is counted exactly once, even when divisibility overlaps occur.
Therefore, the algorithm correctly identifies the smallest number whose count reaches n, which is precisely the nth ugly number.
Python Solution
import math
class Solution:
def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
def lcm(x: int, y: int) -> int:
return x * y // math.gcd(x, y)
ab = lcm(a, b)
ac = lcm(a, c)
bc = lcm(b, c)
abc = lcm(ab, c)
def count_ugly(x: int) -> int:
return (
x // a +
x // b +
x // c -
x // ab -
x // ac -
x // bc +
x // abc
)
left = 1
right = 2 * 10**9
while left < right:
mid = (left + right) // 2
if count_ugly(mid) >= n:
right = mid
else:
left = mid + 1
return left
The implementation starts by defining an lcm helper function using the relationship between GCD and LCM:
$\mathrm{lcm}(x,y)=\frac{x\cdot y}{\gcd(x,y)}$
We then precompute all pairwise and triple least common multiples. These are reused repeatedly during binary search, so precomputing avoids redundant calculations.
The count_ugly function applies the Inclusion-Exclusion Principle to determine how many valid numbers exist up to x.
Binary search then narrows the answer range. If the current midpoint already contains at least n ugly numbers, the solution may be smaller, so the search moves left. Otherwise, it moves right.
When the loop finishes, left is the smallest value satisfying the condition, which is exactly the nth ugly number.
Go Solution
package main
func nthUglyNumber(n int, a int, b int, c int) int {
gcd := func(x, y int64) int64 {
for y != 0 {
x, y = y, x%y
}
return x
}
lcm := func(x, y int64) int64 {
return x / gcd(x, y) * y
}
A := int64(a)
B := int64(b)
C := int64(c)
ab := lcm(A, B)
ac := lcm(A, C)
bc := lcm(B, C)
abc := lcm(ab, C)
countUgly := func(x int64) int64 {
return (
x/A +
x/B +
x/C -
x/ab -
x/ac -
x/bc +
x/abc
)
}
left := int64(1)
right := int64(2 * 1000000000)
for left < right {
mid := left + (right-left)/2
if countUgly(mid) >= int64(n) {
right = mid
} else {
left = mid + 1
}
}
return int(left)
}
The Go implementation closely mirrors the Python version, but there are some important language-specific details.
Go integers can overflow more easily than Python integers because Python supports arbitrary precision integers automatically. Since intermediate LCM calculations may exceed 32-bit integer limits, the implementation uses int64 throughout the calculation logic.
The binary search midpoint is computed using:
mid := left + (right-left)/2
This form avoids potential overflow that could occur with (left + right) / 2.
Anonymous helper functions are used for gcd, lcm, and countUgly, which keeps the implementation compact and self-contained.
Worked Examples
Example 1
Input:
n = 3, a = 2, b = 3, c = 5
We first compute:
| Value | Result |
|---|---|
| lcm(2,3) | 6 |
| lcm(2,5) | 10 |
| lcm(3,5) | 15 |
| lcm(2,3,5) | 30 |
Suppose binary search checks mid = 4.
The count becomes:
| Expression | Value |
|---|---|
| 4 // 2 | 2 |
| 4 // 3 | 1 |
| 4 // 5 | 0 |
| 4 // 6 | 0 |
| 4 // 10 | 0 |
| 4 // 15 | 0 |
| 4 // 30 | 0 |
Total:
2 + 1 + 0 - 0 - 0 - 0 + 0 = 3
Since the count is 3, we know the third ugly number is at most 4.
Eventually binary search converges to:
Answer = 4
Example 2
Input:
n = 4, a = 2, b = 3, c = 4
Computed LCMs:
| Value | Result |
|---|---|
| lcm(2,3) | 6 |
| lcm(2,4) | 4 |
| lcm(3,4) | 12 |
| lcm(2,3,4) | 12 |
Check mid = 6.
| Expression | Value |
|---|---|
| 6 // 2 | 3 |
| 6 // 3 | 2 |
| 6 // 4 | 1 |
| 6 // 6 | 1 |
| 6 // 4 | 1 |
| 6 // 12 | 0 |
| 6 // 12 | 0 |
Total:
3 + 2 + 1 - 1 - 1 - 0 + 0 = 4
So there are exactly four ugly numbers up to 6:
2, 3, 4, 6
Therefore:
Answer = 6
Example 3
Input:
n = 5, a = 2, b = 11, c = 13
Ugly numbers begin as:
2, 4, 6, 8, 10, 11, 12, 13...
The fifth ugly number is clearly:
10
Binary search will eventually identify the smallest value whose count reaches 5.
For mid = 10:
| Expression | Value |
|---|---|
| 10 // 2 | 5 |
| 10 // 11 | 0 |
| 10 // 13 | 0 |
All overlap terms are zero.
Total:
5
So:
Answer = 10
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(log(2 × 10^9)) | Binary search performs about 31 iterations |
| Space | O(1) | Only constant extra variables are used |
The binary search range is fixed between 1 and 2 * 10^9. Since binary search halves the range each iteration, the total number of iterations is approximately:
$\log_2(2\times10^9)\approx31$
Each iteration performs only constant-time arithmetic operations, including GCD, LCM, and division calculations.
The algorithm uses constant additional memory because it stores only a small fixed number of integers.
Test Cases
# Provided examples
assert Solution().nthUglyNumber(3, 2, 3, 5) == 4 # Basic example
assert Solution().nthUglyNumber(4, 2, 3, 4) == 6 # Overlapping divisors
assert Solution().nthUglyNumber(5, 2, 11, 13) == 10 # Sparse divisors
# Single divisor dominance
assert Solution().nthUglyNumber(1, 2, 3, 5) == 2 # First ugly number
assert Solution().nthUglyNumber(5, 2, 4, 8) == 10 # All multiples overlap heavily
# Equal divisors
assert Solution().nthUglyNumber(7, 3, 3, 3) == 21 # Same divisor repeated
# Pairwise overlap
assert Solution().nthUglyNumber(6, 2, 4, 6) == 12 # Many duplicate counts
# Large values
assert Solution().nthUglyNumber(1000000000, 2, 217983653, 336916467) > 0 # Stress test
# Prime divisors
assert Solution().nthUglyNumber(8, 7, 11, 13) == 28 # Sparse ugly numbers
# One divisor equals one
assert Solution().nthUglyNumber(100, 1, 2, 3) == 100 # Every number is ugly
| Test | Why |
|---|---|
n=3, a=2, b=3, c=5 |
Validates basic functionality |
n=4, a=2, b=3, c=4 |
Tests overlap handling |
n=5, a=2, b=11, c=13 |
Tests sparse distributions |
n=1, a=2, b=3, c=5 |
Smallest possible n |
n=5, a=2, b=4, c=8 |
Heavy overlap between divisors |
n=7, a=3, b=3, c=3 |
Identical divisors |
n=6, a=2, b=4, c=6 |
Multiple inclusion-exclusion overlaps |
n=1000000000, ... |
Performance and upper-bound stress |
n=8, a=7, b=11, c=13 |
Prime divisors with sparse ugly numbers |
n=100, a=1, b=2, c=3 |
Every integer becomes ugly |
Edge Cases
One important edge case occurs when all divisors are the same. For example, a = b = c = 3. A naive implementation might count multiples of 3 three separate times and produce incorrect results. The Inclusion-Exclusion Principle handles this correctly because overlapping counts are subtracted appropriately. The sequence simply becomes 3, 6, 9, 12, ....
Another tricky case occurs when one divisor is a multiple of another, such as a = 2, b = 4, c = 8. Every multiple of 4 and 8 is already a multiple of 2. Without careful overlap correction, duplicates would inflate the count dramatically. The least common multiple calculations ensure these duplicate counts are removed correctly.
Large input values are also critical. Since a, b, and c may approach 10^9, intermediate multiplication during LCM computation can overflow standard integer types in some languages. The Go implementation uses int64 specifically to prevent overflow. Python avoids this issue automatically because integers have arbitrary precision.
A final edge case occurs when one divisor equals 1. In that situation, every positive integer is ugly because all numbers are divisible by 1. The algorithm still works naturally because the counting function becomes count(x) = x, and binary search correctly returns n.