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

# 0264. Ugly Number II

<https://leetcode.com/problems/ugly-number-ii>

## Description

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`

## ac1: PriorityQueue, or TreeSet

Key: TreeSet can replace PriorityQueue, if not repeated element is allowed.

```java
class Solution {
    public int nthUglyNumber(int n) {
        TreeSet<Long> ts = new TreeSet<Long>();
        ts.add(1l);

        for (int i = 1; i < n; i++) {
            Long head = ts.pollFirst();
            ts.add(head * 2);
            ts.add(head * 3);
            ts.add(head * 5);
        }

        return ts.pollFirst().intValue();
    }
}
```

## ac2: DP

```java
class Solution {
    public int nthUglyNumber(int n) {
        int i2 = 0, i3 = 0, i5 = 0;
        int[] dp = new int[n];
        dp[0] = 1;

        for (int i = 1; i < n; i++) {
            dp[i] = Math.min(dp[i2]*2, Math.min(dp[i3]*3, dp[i5]*5));

            if (dp[i] == dp[i2]*2) i2++;
            if (dp[i] == dp[i3]*3) i3++;
            if (dp[i] == dp[i5]*5) i5++;
        }

        return dp[n-1];
    }
}
/**
DP

   i    0   1   2   3   4   5   6   7
 dp[i]  1   2   3   4   5   6   8   9

    i2  2   4   6   8   10  12  18  20
                    △
    i3  3   6   9   12  15  18  27  30
                △
    i5  5   10  15  20  25  30  45  50
        △
**/
```