Problem Statement
Ugly Number II
An "ugly number" is a positive whole number you can build using only the factors 2, 3, and 5. That means if you keep dividing it by 2, 3, and 5, you eventually reach 1. For example, 12 is ugly because 12 = 2 * 2 * 3. But 14 is not ugly, because 14 = 2 * 7, and 7 is not allowed. The number 1 counts as ugly too. Your job: given a number n, find the nth ugly number in order. The list begins 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, and so on. The trick is to build that list in the right order without skipping any and without repeating any. We will look at two ways to do that, and the fast way uses an idea called three pointers.
Signals to notice
Brute force first
Check each number 1, 2, 3,.. for ugliness. Very slow for large n. That instinct is useful because it follows the prompt literally, but it usually keeps revisiting work the problem is begging you to organize.
The key insight
Three pointers: track the next ugly number to multiply by 2, 3, and 5. Take the minimum of the three candidates. Advance the pointer(s) that produced the minimum. The goal is not to be clever for its own sake, but to remember the one relationship that keeps the solution grounded as you move forward.
Trace it on n = 10 (return the 10th ugly number)
init: ugly=[1], i2=i3=i5=0 i=1: min(1*2, 1*3, 1*5)=2 -> ugly=[1,2]; i2->1 i=2: min(2*2, 1*3, 1*5)=3 -> ugly=[1,2,3]; i3->1 i=3: min(2*2, 2*3, 1*5)=4 -> ugly=[..,4]; i2->2 i=4: min(3*2, 2*3, 1*5)=5 -> ugly=[..,5]; i5->1 i=5: min(3*2, 2*3, 2*5)=6 -> ugly=[..,6]; i2->3, i3->2 (tie, advance both) i=6,7,8: -> 8 (i2->4), 9 (i3->3), 10 (i2->5,i5->2) i=9: min(6*2, 4*3, 3*5)=12 -> ugly=[..,12]; i2->6, i3->4 return ugly[9] = 12
What must stay true
Every ugly number is 2, 3, or 5 times a previous ugly number. Three sorted sequences (ugly×2, ugly×3, ugly×5) are merged, and the minimum gives the next ugly number. If that remains true after every update, the rest of the reasoning has a stable place to stand.
Shape of the loop
ugly[0] = 1; i2 = i3 = i5 = 0
for i in 1..n-1:
cand = min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
ugly[i] = cand
advance EACH pointer whose candidate equals cand
return ugly[n-1]Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Not advancing ALL pointers that match the minimum — if ugly[i2]×2 == ugly[i3]×3, advance both to avoid duplicates. Most mistakes here are not about syntax; they come from losing track of what your state, pointer, or structure is supposed to mean.