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.

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

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
        △
**/