264. Ugly Number II

264. Ugly Number II (Medium)

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.

Related Topics:
Math, Dynamic Programming, Heap

Similar Questions:

• Merge k Sorted Lists (Hard)
• Count Primes (Easy)
• Ugly Number (Easy)
• Perfect Squares (Medium)
• Super Ugly Number (Medium)
• Ugly Number III (Medium)

Solution 1. DP

Assume we've already computed the first n ugly numbers and stored them in vector v, the next ugly number must be the smallest one among v[i] * 2 > v[n-1], v[j] * 3] > v[n-1] and v[k] * 5 > v[n-1] where i, j, k are some indexes in range [0, n).

// OJ: https://leetcode.com/problems/ugly-number-ii/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> num(n);
        num[0] = 1;
        int i = 0, j = 0, k = 0;
        for (int t = 1; t < n; ++t) {
            num[t] = min({ num[i] * 2, num[j] * 3, num[k] * 5 });
            if (num[t] == num[i] * 2) ++i;
            if (num[t] == num[j] * 3) ++j;
            if (num[t] == num[k] * 5) ++k;
        }
        return num.back();
    }
};

Another implementation.

// OJ: https://leetcode.com/problems/ugly-number-ii
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> num(n, 1), index(3, 0), val{2, 3, 5};
        for (int i = 1; i < n; ++i) {
            int next = INT_MAX;
            for (int j = 0; j < 3; ++j) next = min(next, num[index[j]] * val[j]);
            for (int j = 0; j < 3; ++j) {
                if (num[index[j]] * val[j] == next) ++index[j];
            }
            num[i] = next;
        }
        return num.back();
    }
};