Problem Description

The Ugly Number II problem asks you to find the nth "ugly number". An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5. In other words, ugly numbers are numbers of the form 2^a * 3^b * 5^c where a, b, c are non-negative integers.

• The sequence of ugly numbers starts with 1 (by convention), followed by 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...
• You are given an integer n (typically 1 ≤ n ≤ 1690), and you must return the nth ugly number in the sequence.
• Each ugly number must be unique. No number should be included more than once in the sequence.
• Only multiplication by 2, 3, and 5 is allowed to generate new ugly numbers from the previous ones.

Thought Process

At first glance, you might consider checking each integer in order and testing if its only prime factors are 2, 3, and 5. However, this brute-force approach is highly inefficient, especially as n increases, because most numbers are not ugly numbers.

Instead, we can notice that every ugly number (after 1) is produced by multiplying a previous ugly number by either 2, 3, or 5. This hints at a way to generate the sequence in order, without skipping or duplicating any numbers. The challenge is to do this efficiently and without generating duplicates.

The key insight is to keep track of the next multiple of 2, 3, and 5 for the ugly numbers we have so far. By always choosing the smallest next candidate, we can build the sequence in order.

Solution Approach

To efficiently generate the sequence of ugly numbers, we use a dynamic programming approach with three pointers. Here’s a step-by-step breakdown:

1. Initialize an array ugly of size n to store the ugly numbers. Set ugly[0] = 1 since 1 is the first ugly number.
2. Maintain three pointers: i2, i3, and i5. These track which ugly number to multiply by 2, 3, and 5 next.
3. At each step, compute the next possible ugly numbers:
   • next2 = ugly[i2] * 2
   • next3 = ugly[i3] * 3
   • next5 = ugly[i5] * 5
4. Select the minimum among next2, next3, and next5 as the next ugly number, and append it to the ugly array.
5. Increment the pointer(s) whose value was used. For example, if next2 was the minimum, increment i2. If multiple values are equal, increment all relevant pointers to avoid duplicates.
6. Repeat until the ugly array contains n numbers.

This approach guarantees that all ugly numbers are generated in ascending order, with no duplicates, and with optimal efficiency.

Example Walkthrough

Let's walk through finding the first 10 ugly numbers (n = 10):

• Start: ugly = [1]
• i2 = 0, i3 = 0, i5 = 0

1. Step 1: next2 = 1*2=2, next3 = 1*3=3, next5 = 1*5=5.
   Min is 2. Add 2 to ugly. Increment i2.
   ugly = [1, 2], i2 = 1, i3 = 0, i5 = 0
2. Step 2: next2 = 2*2=4, next3 = 1*3=3, next5 = 1*5=5.
   Min is 3. Add 3. Increment i3.
   ugly = [1, 2, 3], i2 = 1, i3 = 1, i5 = 0
3. Step 3: next2 = 2*2=4, next3 = 2*3=6, next5 = 1*5=5.
   Min is 4. Add 4. Increment i2.
   ugly = [1, 2, 3, 4], i2 = 2, i3 = 1, i5 = 0
4. Step 4: next2 = 3*2=6, next3 = 2*3=6, next5 = 1*5=5.
   Min is 5. Add 5. Increment i5.
   ugly = [1, 2, 3, 4, 5], i2 = 2, i3 = 1, i5 = 1
5. Step 5: next2 = 3*2=6, next3 = 2*3=6, next5 = 2*5=10.
   Min is 6. Add 6. Both next2 and next3 are 6; increment i2 and i3.
   ugly = [1, 2, 3, 4, 5, 6], i2 = 3, i3 = 2, i5 = 1
6. Step 6: next2 = 4*2=8, next3 = 3*3=9, next5 = 2*5=10.
   Min is 8. Add 8. Increment i2.
   ugly = [1, 2, 3, 4, 5, 6, 8], i2 = 4, i3 = 2, i5 = 1
7. Step 7: next2 = 5*2=10, next3 = 3*3=9, next5 = 2*5=10.
   Min is 9. Add 9. Increment i3.
   ugly = [1, 2, 3, 4, 5, 6, 8, 9], i2 = 4, i3 = 3, i5 = 1
8. Step 8: next2 = 5*2=10, next3 = 4*3=12, next5 = 2*5=10.
   Min is 10. Both next2 and next5 are 10; increment i2 and i5.
   ugly = [1, 2, 3, 4, 5, 6, 8, 9, 10], i2 = 5, i3 = 3, i5 = 2
9. Step 9: next2 = 6*2=12, next3 = 4*3=12, next5 = 3*5=15.
   Min is 12. Both next2 and next3 are 12; increment i2 and i3.
   ugly = [1, 2, 3, 4, 5, 6, 8, 9, 10, 12]

The 10th ugly number is 12.

Time and Space Complexity

• Brute-force approach:
  • For each number, check if it is ugly by dividing by 2, 3, and 5 repeatedly.
  • Most numbers are not ugly numbers, so this is very inefficient for large n.
  • Time complexity: Much worse than O(n), potentially O(n log n) or worse due to checking many candidates.
• Optimized pointer approach:
  • Each new ugly number is generated in constant time by comparing three numbers.
  • We perform n steps, and each step involves a constant amount of work.
  • Time complexity: O(n).
  • Space complexity: O(n) to store the ugly numbers.

Summary

The Ugly Number II problem is a classic example where naive brute-force is too slow, but a clever use of pointers and dynamic programming leads to an efficient solution. By keeping track of which multiples of 2, 3, and 5 to use next, we can generate the sequence of ugly numbers in order, without duplicates, and in linear time. This approach is both elegant and practical, making it a great tool for tackling similar sequence-generation problems.

Code Implementation

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        ugly = [1]
        i2 = i3 = i5 = 0
        
        for _ in range(1, n):
            next2 = ugly[i2] * 2
            next3 = ugly[i3] * 3
            next5 = ugly[i5] * 5
            next_ugly = min(next2, next3, next5)
            ugly.append(next_ugly)
            
            if next_ugly == next2:
                i2 += 1
            if next_ugly == next3:
                i3 += 1
            if next_ugly == next5:
                i5 += 1
        return ugly[-1]
      

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> ugly(n);
        ugly[0] = 1;
        int i2 = 0, i3 = 0, i5 = 0;
        for (int i = 1; i < n; ++i) {
            int next2 = ugly[i2] * 2;
            int next3 = ugly[i3] * 3;
            int next5 = ugly[i5] * 5;
            int next_ugly = min(next2, min(next3, next5));
            ugly[i] = next_ugly;
            if (next_ugly == next2) ++i2;
            if (next_ugly == next3) ++i3;
            if (next_ugly == next5) ++i5;
        }
        return ugly[n - 1];
    }
};
      

class Solution {
    public int nthUglyNumber(int n) {
        int[] ugly = new int[n];
        ugly[0] = 1;
        int i2 = 0, i3 = 0, i5 = 0;
        for (int i = 1; i < n; i++) {
            int next2 = ugly[i2] * 2;
            int next3 = ugly[i3] * 3;
            int next5 = ugly[i5] * 5;
            int nextUgly = Math.min(next2, Math.min(next3, next5));
            ugly[i] = nextUgly;
            if (nextUgly == next2) i2++;
            if (nextUgly == next3) i3++;
            if (nextUgly == next5) i5++;
        }
        return ugly[n - 1];
    }
}
      

var nthUglyNumber = function(n) {
    let ugly = [1];
    let i2 = 0, i3 = 0, i5 = 0;
    for (let i = 1; i < n; i++) {
        let next2 = ugly[i2] * 2;
        let next3 = ugly[i3] * 3;
        let next5 = ugly[i5] * 5;
        let nextUgly = Math.min(next2, next3, next5);
        ugly.push(nextUgly);
        if (nextUgly === next2) i2++;
        if (nextUgly === next3) i3++;
        if (nextUgly === next5) i5++;
    }
    return ugly[n - 1];
};