A super ugly number is a positive integer whose prime factors are in the array primes.

Given an integer n and an array of integers primes, return the nth super ugly number.

The nth super ugly number is guaranteed to fit in a 32-bit signed integer.

&nbsp;
Example 1:

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].


Example 2:

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


&nbsp;
Constraints:


	1 &lt;= n &lt;= 105
	1 &lt;= primes.length &lt;= 100
	2 &lt;= primes[i] &lt;= 1000
	primes[i] is guaranteed to be a prime number.
	All the values of primes are unique and sorted in ascending order.


class Solution:
def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
    prime_nums = len(primes)
    index = [1]*prime_nums
    ret = [1]*(n+1)
    for i in range(2,n+1):
        ret[i] = min(primes[j]*ret[index[j]] for j in range(prime_nums))
        for k in range(prime_nums):
            if ret[i] == primes[k]*ret[index[k]]:
                index[k]+= 1
    
    return ret[-1]
//---------------------O(nlogk)-------------------------

class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int []dp=new int[n+1];
        dp[1]=1;
        
        PriorityQueue<Pair> pq=new PriorityQueue<>();
        
        for(int i=0;i<primes.length;i++){
            pq.add(new Pair(primes[i],1,primes[i]));
        }
        
        for(int i=2;i<=n;){
            Pair curr=pq.remove();
            
            if(curr.val!=dp[i-1]){
                dp[i]=curr.val;
                i++;
            }
            
            int newval=curr.prime*dp[curr.ptr+1];
            if(newval>0){
                pq.add(new Pair(curr.prime, curr.ptr+1,newval));
            }
        }
        
        return dp[n];
    }
}

class Pair implements Comparable<Pair>{
    int prime;
    int ptr;
    int val;
    
    public Pair(int prime, int ptr, int val){
        this.prime=prime;
        this.ptr=ptr;
        this.val=val;
    }
    
    public int compareTo(Pair o){
        return this.val-o.val;
    }
}

//-----------------------O(nk)---------------------------

// class Solution {
//     public int nthSuperUglyNumber(int n, int[] primes) {
//         int []dp=new int[n+1];
//         dp[1]=1;
        
//         int []ptr=new int[primes.length];
        
//         Arrays.fill(ptr,1);
        
//         for(int i=2;i<=n;i++){
            
//             int min=Integer.MAX_VALUE;
            
//             for(int j=0;j<ptr.length;j++){
//                 int val=dp[ptr[j]]*primes[j];
//                 if(val>0){
//                     min=Math.min(min,val);
//                 }
                
//             }
            
//             dp[i]=min;
            
//             for(int j=0;j<ptr.length;j++){
//                 int val=dp[ptr[j]]*primes[j];
//                 if(val>0 && min==val){
//                     ptr[j]++;
//                 }
//             }
//         }
        
//         return dp[n];
//     }
// }
Time: O(n*n1)  Space: O(n)

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        if(n==1)
            return 1;
        vector<long long int> dp(n);
        dp[0]=1;
        int n1=size(primes);
        vector<int> p(n1);
        for(int i=1;i<n;i++){
             long long int x=INT_MAX;
            for(int j=0;j<n1;j++){
                x=min(x,primes[j]*dp[p[j]]);
            }
            dp[i]=x;
            for(int j=0;j<n1;j++){
                if(x==primes[j]*dp[p[j]])
                    p[j]++;
            }
        }
        return dp[n-1];
    }
};
var nthSuperUglyNumber = function(n, primes) {
    const table = Array(primes.length).fill(0);
    const res = Array(n);
    res[0] = 1;
    for(let j=1;j<n;j++){
        let curr = Infinity;
        for (let i=0;i< table.length; i++) {
            curr = Math.min(curr, res[table[i]]*primes[i]);
        }
        for (let i=0;i< table.length; i++) {
            if (curr === res[table[i]]*primes[i]) table[i]++;
        }
        res[j] = curr;
    }
    return res[n-1];
};
Super Ugly Number