<p>A <strong>super ugly number</strong> is a positive integer whose prime factors are in the array <code>primes</code>.</p>

<p>Given an integer <code>n</code> and an array of integers <code>primes</code>, return <em>the</em> <code>n<sup>th</sup></code> <em><strong>super ugly number</strong></em>.</p>

<p>The <code>n<sup>th</sup></code> <strong>super ugly number</strong> is <strong>guaranteed</strong> to fit in a <strong>32-bit</strong> signed integer.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 12, primes = [2,7,13,19]
<strong>Output:</strong> 32
<strong>Explanation:</strong> [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].
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 1, primes = [2,3,5]
<strong>Output:</strong> 1
<strong>Explanation:</strong> 1 has no prime factors, therefore all of its prime factors are in the array primes = [2,3,5].
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= primes.length &lt;= 100</code></li>
	<li><code>2 &lt;= primes[i] &lt;= 1000</code></li>
	<li><code>primes[i]</code> is <strong>guaranteed</strong> to be a prime number.</li>
	<li>All the values of <code>primes</code> are <strong>unique</strong> and sorted in <strong>ascending order</strong>.</li>
</ul>

class Solution {
public:
    int solve(int n, vector<int>& primes){
        long long dp[n];
        dp[0] = 1l;

        int m = primes.size();
        int p[m];
        for(int i = 0; i < m; i++) p[i] = 0;

        for(int i = 1; i < n; i++){
            long long Min = LONG_MAX;
            for(int pi = 0; pi < m; pi++){
                Min = min(Min, (long long)primes[pi] * dp[p[pi]]);
            }
            dp[i] = Min;

            for(int pi = 0; pi < m; pi++){
                if(Min == (long long)primes[pi] * dp[p[pi]]){
                    p[pi]++;
                }
            }
        }

        return dp[n - 1];
    }

    int nthSuperUglyNumber(int n, vector<int>& primes) {
        // M - 1 : same as ugly number
        // return solve(n, primes);

        // M - 2: Optimized Approach (using priority_queue)
        long long dp[n + 1];
        dp[1] = 1l;

        auto comp = [](vector<long long>& a, vector<long long>& b) {
            return a[0] > b[0];                             // min pq
        };

        priority_queue<vector<long long>, vector<vector<long long>>, decltype(comp)> pq(comp);      // value, index, primes[i]
       
        for(int i = 0; i < primes.size(); i++){
            // pq.push({1l, {1, (long long)primes[i]}});
            pq.push({(long long)primes[i], 1, (long long)primes[i]});
        }

        for(int i = 2; i <= n; ){
            if(pq.top()[0] != dp[i - 1]){
                dp[i] = pq.top()[0];
                i++;
            }

            vector<long long> p = pq.top();
            pq.pop();
            p[1]++;
            p[0] = (long long)p[2] * dp[p[1]];                         // primes[i] * dp[index]
            pq.push(p);
        }

        return dp[n];
    }
};
99150