Ugly Number II
Ugly Number II: find the nth number whose only prime factors are 2, 3, and 5.
- 1 <= n <= 1690
Intuition
Ugly number ii finds the n-th ugly number — the n-th positive integer whose only prime factors are 2, 3, and 5. Testing each integer in turn works but is far too slow, since ugly numbers thin out rapidly.
The productive change is to generate them rather than test candidates:
- Every ugly number after 1 is some earlier ugly number multiplied by 2, 3, or 5 — so the sequence builds from itself.
That suggests multiplying every known ugly number by all three factors and taking the smallest unused result. Doing that naively with a heap works, at O(n log n) with duplicate handling.
The better solution uses three pointers, one per factor. Each pointer marks the earliest ugly number not yet multiplied by its factor. The next ugly number is the minimum of the three candidate products.
After choosing it, every pointer whose product equals that minimum advances — not just one. This is the crux: 6 arises as both 2 × 3 and 3 × 2, so advancing a single pointer leaves the duplicate to be emitted again.
Using separate if statements rather than else if is what handles that correctly, and it is the single most common bug in the problem.
All three pointers start at index 0, and the sequence starts with 1.
The sequence is generated in ascending order by construction, so no sorting is needed and the n-th element is simply the last one produced.
Each of n values costs constant work, giving O(n) time and O(n) space for the sequence.
Three pointers into the sequence being built, each producing candidates by multiplying an earlier ugly number by 2, 3, or 5. Every ugly number is some earlier one times one of those primes, so the next value is always the minimum of the three candidates.
Approach
Before reading on: price up what the direct approach costs here, then ask what a single cell should mean, and which earlier cells it needs. Aim for O(n) time and O(n) space.
Generate rather than test
Every ugly number is an earlier one times 2, 3, or 5, so the sequence builds from itself. Testing each integer is far too slow.
Keep three pointers
One pointer per factor marks the earliest ugly number not yet multiplied by it. Three candidate products are always available.
Take the smallest candidate
The next ugly number is the minimum of the three products. The sequence is generated in ascending order, so no sorting is ever needed.
Advance every matching pointer
Use separate if statements, not else if. 6 arises as both 2 × 3 and 3 × 2 — advancing only one pointer emits the duplicate again.
Seed with one
The sequence begins at 1 with all three pointers at index 0. Every later value derives from it.
Cost of the approach
Each of n values costs constant work, giving O(n) time and O(n) space — better than the heap version's O(n log n).
Solution & live demo
Common pitfalls
Using elif for the pointer advances
if c2 == nxt: p2 += 1 elif c3 == nxt: p3 += 1
if c2 == nxt: p2 += 1 if c3 == nxt: p3 += 1 if c5 == nxt: p5 += 1
Candidates can tie — 6 is both 3×2 and 2×3. Advancing only one pointer leaves the other producing 6 again, so duplicates enter the sequence and every later index is shifted.
Testing each number for ugliness
i = 0 while count < n: i += 1; if isUgly(i): count += 1
nxt = min(c2, c3, c5)
Ugly numbers thin out fast — the 1690th is over two billion, so scanning every integer up to it times out. Generating only ugly numbers visits exactly n values.
Returning dp[n]
return dp[n]
return dp[n - 1]
The list is zero-indexed and holds exactly n entries when the loop ends, so the n-th ugly number sits at index n - 1. Reading dp[n] runs past the end.
Edge cases
the sequence already contains just [1] and no loop iterations run, so the answer is 1
e.g. dp[p2]2 == dp[p3]3 == 6, both pointers advance in the same step, not just one
the sequence grows by exactly one entry per iteration, so building it takes O(n) total work
the other two pointers simply sit still until their candidate becomes the minimum again