> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/ugly-number-ii.md).

# Ugly Number II

Write a program to find the `n`-th ugly number.

Ugly numbers are **positive numbers** whose prime factors only include `2, 3, 5`. 

**Example:**

```
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.
```

**Note:** 

1. `1` is typically treated as an ugly number.
2. `n` **does not exceed 1690**.

```java
class Solution {
    public int nthUglyNumber(int n) {
        if (n <= 0)
            return 0;
        if (n == 1)
            return 1;
        int dp[] = new int[n];
        // 1st ugly number is 1
        dp[0] = 1;
        int p2 = 0, p3 = 0, p5 = 0;
        for (int i = 1; i < n; i++) {
            int option1 = 2 * dp[p2];
            int option2 = 3 * dp[p3];
            int option3 = 5 * dp[p5];
            dp[i] = Math.min(option1, Math.min(option2, option3));
            if (dp[i] == option1)
                p2++;
            if (dp[i] == option2)
                p3++;
            if (dp[i] == option3)
                p5++;
        }
        return dp[n - 1];
    }
}
```