LeetCode 264: Ugly Number II

Problem Restatement

We are given an integer n.

Return the nth ugly number.

An ugly number is a positive integer whose prime factors are limited to:

2, 3, 5

The sequence starts with:

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ...

1 is treated as an ugly number.

The constraint is:

1 <= n <= 1690

The official examples include n = 10 -> 12 and n = 1 -> 1.

Input and Output

Example function shape:

def nthUglyNumber(n: int) -> int:
    ...

Examples

Example 1:

n = 10

The first ten ugly numbers are:

1, 2, 3, 4, 5, 6, 8, 9, 10, 12

The 10th ugly number is:

12

Answer:

12

Example 2:

n = 1

The first ugly number is:

1

Answer:

1

First Thought: Check Every Integer

A direct approach is to test every positive integer.

For each number, use the method from LeetCode 263:

1. Divide out all factors of 2.
2. Divide out all factors of 3.
3. Divide out all factors of 5.
4. If the result is 1, the number is ugly.

Keep counting ugly numbers until the nth one appears.

This works, but it wastes time checking many numbers that are not ugly.

Problem With Brute Force

The ugly numbers become more spread out as values grow.

Checking every integer means we spend work on numbers like:

7, 11, 13, 14, 17, 19, 21, ...

Most of these contain forbidden prime factors.

Instead of checking all numbers, we should generate ugly numbers directly.

Key Insight

Every ugly number after 1 comes from a smaller ugly number multiplied by one of:

2, 3, 5

So if we already know the ugly sequence, the next ugly number must be the smallest value among:

some_previous_ugly * 2
some_previous_ugly * 3
some_previous_ugly * 5

We maintain three pointers:

At each step, the next ugly number is:

min(ugly[i2] * 2, ugly[i3] * 3, ugly[i5] * 5)

After choosing the next number, advance every pointer that produced it.

Advancing every matching pointer is important because duplicates can be generated in multiple ways.

For example:

6 = 2 * 3 = 3 * 2

We should include 6 only once.

Algorithm

1. Create an array ugly of length n.
2. Set:

   ugly[0] = 1
3. Start three pointers:

   i2 = i3 = i5 = 0
4. For each next position from 1 to n - 1:
   • Compute:

     next2 = ugly[i2] * 2
     next3 = ugly[i3] * 3
     next5 = ugly[i5] * 5
   • Let:

     nxt = min(next2, next3, next5)
   • Store nxt in the sequence.
   • If nxt == next2, increment i2.
   • If nxt == next3, increment i3.
   • If nxt == next5, increment i5.
5. Return:

   ugly[n - 1]

Walkthrough

Use:

n = 10

Start:

ugly = [1]
i2 = 0
i3 = 0
i5 = 0

Candidates:

So the first ten ugly numbers are:

[1, 2, 3, 4, 5, 6, 8, 9, 10, 12]

Return:

12

Correctness

The array ugly is built in increasing order.

Initially, ugly[0] = 1, which is the first ugly number.

Every later ugly number must be formed by multiplying a smaller ugly number by 2, 3, or 5. Therefore, the next possible ugly number must be one of the three candidate streams:

ugly[i2] * 2
ugly[i3] * 3
ugly[i5] * 5

The pointers always refer to the first candidate in each stream that has not already been passed.

Taking the minimum of these three candidates gives the smallest ugly number not yet added.

When the chosen value equals one or more candidate streams, all matching pointers are advanced. This removes duplicates such as 6, 10, 15, and 30, which can be produced by more than one factor path.

Thus each step appends exactly the next ugly number, in order, without duplicates.

After filling n values, ugly[n - 1] is the nth ugly number.

Complexity

Implementation

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        ugly = [1] * n

        i2 = 0
        i3 = 0
        i5 = 0

        for i in range(1, n):
            next2 = ugly[i2] * 2
            next3 = ugly[i3] * 3
            next5 = ugly[i5] * 5

            nxt = min(next2, next3, next5)
            ugly[i] = nxt

            if nxt == next2:
                i2 += 1
            if nxt == next3:
                i3 += 1
            if nxt == next5:
                i5 += 1

        return ugly[n - 1]

Code Explanation

The array starts with 1:

ugly = [1] * n

The first value is already correct, so we fill from index 1.

The three pointers start at the first ugly number:

i2 = 0
i3 = 0
i5 = 0

At every step, compute the next possible value from each multiplication stream:

next2 = ugly[i2] * 2
next3 = ugly[i3] * 3
next5 = ugly[i5] * 5

The smallest candidate becomes the next ugly number:

nxt = min(next2, next3, next5)
ugly[i] = nxt

Then advance every pointer that produced nxt:

if nxt == next2:
    i2 += 1
if nxt == next3:
    i3 += 1
if nxt == next5:
    i5 += 1

Using three separate if statements removes duplicates.

Finally:

return ugly[n - 1]

returns the nth ugly number.

Testing

def run_tests():
    s = Solution()

    assert s.nthUglyNumber(1) == 1
    assert s.nthUglyNumber(2) == 2
    assert s.nthUglyNumber(3) == 3
    assert s.nthUglyNumber(10) == 12
    assert s.nthUglyNumber(11) == 15
    assert s.nthUglyNumber(15) == 24
    assert s.nthUglyNumber(1690) == 2123366400

    print("all tests passed")

run_tests()

Test meaning: