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.

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

python

▶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

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

06

Complexity

Time

O(n)

Space

O(n)

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