1. Problem Description

You are asked to find the n-th ugly number.

An ugly number is a positive integer whose prime factors are only 2, 3, or 5.
The sequence of ugly numbers starts with:

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

Your task:
Given an integer n, return the n-th ugly number.

---

2. Example

Input:
n = 10

Output:
12

Explanation:
The first 10 ugly numbers are:
[1, 2, 3, 4, 5, 6, 8, 9, 10, 12]

---

3. Naive Approach (Brute Force)

1. Start from 1 and check if each number is ugly.
2. Divide the number by 2, 3, and 5 as long as possible.
3. If the result becomes 1, it’s an ugly number.

However, this is too slow for large n (e.g., 1690), because we’d check many numbers.

Time Complexity: O(n log n) or worse
Space Complexity: O(1)

---

4. Optimized Dynamic Programming Approach

The key observation:

• Every ugly number can be obtained by multiplying a smaller ugly number by either 2, 3, or 5.
• To generate ugly numbers in sorted order, we can maintain three pointers (p2, p3, p5) that track the next multiple of 2, 3, and 5 respectively.

Steps:

1. Initialize an array dp[n] where dp[i] represents the i-th ugly number.
2. Start with dp[0] = 1 (since 1 is considered ugly).
3. Maintain:
   • p2, p3, p5 = indices for next multiples of 2, 3, and 5.
4. For each i:
   • Compute next2 = dp[p2] * 2
   • Compute next3 = dp[p3] * 3
   • Compute next5 = dp[p5] * 5
   • Choose the minimum of these three.
   • If a number is chosen, increment the corresponding pointer(s).

---

5. Code Implementation (Java)

public class UglyNumberII {
    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 nextUgly = Math.min(next2, Math.min(next3, next5));
            dp[i] = nextUgly;

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

        return dp[n - 1];
    }

    public static void main(String[] args) {
        UglyNumberII obj = new UglyNumberII();
        int n = 10;
        System.out.println("The " + n + "th ugly number is " + obj.nthUglyNumber(n));
    }
}

---

6. Dry Run

Input: n = 10

i	dp array so far	p2	p3	p5	next2	next3	next5	nextUgly
0	[1]	0	0	0	2	3	5	–
1	[1, 2]	1	0	0	4	3	5	2
2	[1, 2, 3]	1	1	0	4	6	5	3
3	[1, 2, 3, 4]	2	1	0	6	6	5	4
4	[1, 2, 3, 4, 5]	2	1	1	6	6	10	5
5	[1, 2, 3, 4, 5, 6]	3	2	1	8	9	10	6
6	[1, 2, 3, 4, 5, 6, 8]	4	2	1	10	9	10	8
7	[1, 2, 3, 4, 5, 6, 8, 9]	4	3	1	10	12	10	9
8	[1, 2, 3, 4, 5, 6, 8, 9, 10]	5	3	2	12	12	15	10
9	[1, 2, 3, 4, 5, 6, 8, 9, 10, 12]	6	4	2	16	15	15	12

Result: 12

---

7. Time and Space Complexity

• Time Complexity: O(n) (one iteration per number)
• Space Complexity: O(n) (for the DP array)

---

8. Key Insights

• The three-pointer technique avoids duplicates and ensures sorted order.
• The sequence grows in linear time with no sorting or heap operations.
• This approach is significantly faster and used in many similar problems (like “Super Ugly Number”).