LeetCode #264 Medium

Ugly Number II

Find the nth number whose only prime factors are 2, 3, and 5.

dynamic-programmingheapmath

02

Intuition

Testing every integer in turn to see whether it factors into only 2s, 3s, and 5s is far too slow once n grows. Build the sequence forward instead: every ugly number, after the first, is some earlier ugly number multiplied by 2, 3, or 5. Keep three pointers into the sequence built so far, one per factor, and at each step take the minimum of the three candidate products. The easy mistake is advancing only the pointer that produced the minimum -- when two or three candidates tie for the minimum, EVERY pointer that produced it must advance, or a value like 6 (which is both 2x3 and 3x2) gets appended twice.

How to spot this pattern

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.

03

Approach

1

Seed the sequence and three pointers

Start the sequence with just [1], since 1 is ugly by definition, and initialize three pointers p2, p3, p5 all at index 0 -- each pointing at the earlier ugly number that factor should multiply next.

2

Repeatedly take the minimum of three candidates

At each step compute dp[p2]2, dp[p3]3, dp[p5]*5, take their minimum, and append it to the sequence. This minimum is guaranteed to be the next ugly number, since nothing smaller can be built from the numbers already in the sequence.

3

Advance every pointer that matched the minimum

Compare the minimum against all three candidates, not just the one that happened to be checked first, and increment every pointer whose candidate equals the minimum. This is what prevents duplicate values like 6 or 12 from being inserted more than once.

04

Solution & live demo

▶1class Solution:
▶2    def nthUglyNumber(self, n: int) -> int:
▶3        dp = [1]
▶4        p2 = p3 = p5 = 0
▶5        while len(dp) < n:
▶6            c2, c3, c5 = dp[p2] * 2, dp[p3] * 3, dp[p5] * 5
▶7            nxt = min(c2, c3, c5)
▶8            dp.append(nxt)
▶9            if c2 == nxt:
▶10                p2 += 1
▶11            if c3 == nxt:
▶12                p3 += 1
▶13            if c5 == nxt:
▶14                p5 += 1
▶15        return dp[n - 1]

05

Common pitfalls

Using elif for the pointer advances

✗ Wrong

if c2 == nxt: p2 += 1
elif c3 == nxt: p3 += 1

✓ Right

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

✗ Wrong

i = 0
while count < n: i += 1; if isUgly(i): count += 1

✓ Right

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]

✗ Wrong

return dp[n]

✓ Right

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.

06

Edge cases

n = 1

the sequence already contains just [1] and no loop iterations run, so the answer is 1

multiple candidates tie exactly

e.g. dp[p2]2 == dp[p3]3 == 6, both pointers advance in the same step, not just one

n moderately large

the sequence grows by exactly one entry per iteration, so building it takes O(n) total work

only one factor ever needed for a while

the other two pointers simply sit still until their candidate becomes the minimum again

07

Complexity

Time

O(n)

Space

O(n)

each of the n entries is produced with O(1) work; no primality testing of arbitrary integers.