Ugly Number II

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.

Given an integer n, return the nth ugly number.

Example 1:

Input: n = 10 Output: 12 Explanation: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] is the sequence of the first 10 ugly numbers.

Example 2:

Input: n = 1 Output: 1 Explanation: 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.

Constraints:

• 1 <= n <= 1690

Approach: Dynamic Programming with Three Pointers

Algorithm

1. Every ugly number is 2, 3, or 5 times a smaller ugly number
2. Keep an array dp where dp[i] is the (i+1)-th ugly number
3. Use three pointers p2, p3, p5 tracking the index that produced the last multiple for each factor
4. The next ugly number is the minimum of 2*dp[p2], 3*dp[p3], 5*dp[p5]; advance the pointers whose product equals the minimum to avoid duplicates

Time & Space Complexity

• Time Complexity: O(n) - one pass with constant work per element
• Space Complexity: O(n) - the DP array

Java Implementation

public class UglyNumberII {

    /**
     * Return the nth ugly number.
     * @param n 1-based index
     * @return The nth ugly number
     */
    public int nthUglyNumber(int n) {
        int[] dp = new int[n];
        dp[0] = 1;

        int p2 = 0, p3 = 0, p5 = 0;

        for (int i = 1; i < n; i++) {
            int next2 = dp[p2] * 2;
            int next3 = dp[p3] * 3;
            int next5 = dp[p5] * 5;

            int next = Math.min(next2, Math.min(next3, next5));
            dp[i] = next;

            if (next == next2) {
                p2++;
            }
            if (next == next3) {
                p3++;
            }
            if (next == next5) {
                p5++;
            }
        }

        return dp[n - 1];
    }

    // Test method
    public static void main(String[] args) {
        UglyNumberII u = new UglyNumberII();
        System.out.println("Input: n = 10");
        System.out.println("Output: " + u.nthUglyNumber(10)); // Expected: 12

        System.out.println("Input: n = 1");
        System.out.println("Output: " + u.nthUglyNumber(1)); // Expected: 1
    }
}

Example Walkthrough

Building the first few ugly numbers:

1. dp[0] = 1; p2=p3=p5=0
2. candidates: 2, 3, 5 -> dp[1] = 2, advance p2
3. candidates: 4, 3, 5 -> dp[2] = 3, advance p3
4. candidates: 4, 6, 5 -> dp[3] = 4, advance p2
5. candidates: 6, 6, 5 -> dp[4] = 5, advance p5
6. candidates: 6, 6, 10 -> dp[5] = 6, advance p2 and p3 (both produce 6)

Sequence: 1, 2, 3, 4, 5, 6, … and dp[9] = 12 for n = 10.

Key Points

1. Multiplicative Generation: Every ugly number derives from a smaller one multiplied by 2, 3, or 5
2. Three Pointers: Each pointer records how far its factor has been consumed
3. Duplicate Elimination: Advancing every pointer whose product equals the minimum prevents repeated values
4. Min Selection: The next number is always the smallest available candidate
5. n Bounded: With n up to 1690, the DP array is small and the O(n) pass is fast