# 313. Super Ugly Number

Write a program to find the nth super ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k.

Example:

Input: n = 12, primes = [2,7,13,19]
Output: 32 
Explanation: [1,2,4,7,8,13,14,16,19,26,28,32] is the sequence of the first 12 
             super ugly numbers given primes = [2,7,13,19] of size 4.

Note:

  • 1 is a super ugly number for any given primes.
  • The given numbers in primes are in ascending order.
  • 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.
  • The nth super ugly number is guaranteed to fit in a 32-bit signed integer.

# Solution

Approach 1: Minimum heap.

# Code (Python)

Approach 1:

# Code (C++)

Approach 1:

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        priority_queue<long, vector<long>, greater<long>> minHeap;
        minHeap.push(1);
        long num;
        for (int i = 0; i < n; ++i)
        {
            num = minHeap.top();
            while (!minHeap.empty() && minHeap.top() == num)
                minHeap.pop();
            for (int j = 0; j < primes.size(); ++j)
                minHeap.push(num * primes[j]);
        }
        return num;
    }
};

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        int k = primes.size();
        if (n == 0 || k == 0)
            return 0;
        int ugly[n+1];
        ugly[0] = 0;
        ugly[1] = 1;
        vector<int> idx(k, 1);
        for (int i = 2; i <= n; ++i) {
            int min = INT_MAX;
            for (int j = 0; j < k; ++j) {
                if (ugly[idx[j]] * primes[j] == ugly[i-1])
                    idx[j]++;
                min = std::min(min, ugly[idx[j]] * primes[j]);
            }
            ugly[i] = min;
        }
        return ugly[n];
    }
};