313. Super Ugly Number

Description

Solution

Use priority_queue to find the smallest number

Be careful about integer overflow.

Code

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        priority_queue<long, vector<long>, greater<>> pq;
        long top;
        pq.push(1);
        while(n--){
            top = pq.top();
            while(!pq.empty() && pq.top() == top)
                pq.pop();
            for(auto prime: primes)
                pq.push(top * prime);
        }
        return (int)top;
    }
};