264. Ugly Number II

• Difficulty: Medium

• Topics: Math, Dynamic Programming, Heap

• Similar Questions:

  • Merge k Sorted Lists

  • Count Primes

  • Ugly Number

  • Perfect Squares

  • Super Ugly Number

Problem:

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.

Solutions:

class Solution {
public:
    struct UglyNumber{
        int val;
        int prime;
        int index;

        UglyNumber(int val, int prime, int index) {
            this->val = val;
            this->prime = prime;
            this->index = index;
        }

        bool operator>(const UglyNumber& other) const {
            return val*prime > other.val*other.prime;
        } 
    };

    int nthUglyNumber(int n) {
        vector<int> primes {2, 3, 5}; 
        vector<int> dp(n, 0);
        dp[0] = 1;
        priority_queue<UglyNumber, vector<UglyNumber>, greater<UglyNumber>> pq;
        for (auto prime : primes) {
            pq.push({1, prime, 0});
        }

        for (int i = 1; i < n; ++i) {
            do {
                UglyNumber ugly = pq.top(); pq.pop();
                dp[i] = ugly.val * ugly.prime;
                pq.push({dp[ugly.index + 1], ugly.prime, ugly.index + 1});
            } while (pq.top().val * pq.top().prime == dp[i]);

        }

        return dp[n-1];
    }
};