Cpp solution using DP


  • 0
    G
    int nthSuperUglyNumber(int n, vector<int>& primes) {
    
        if(n==1) return 1;
        vector<int> res(1,1);
        
        int size=primes.size();
        vector<int> prime_num(size,0);
        vector<int> mi(size,1);
        while(res.size()<n){
            int mn=INT_MAX;
            for(int i=0;i<size;i++){
                mi[i]=res[prime_num[i]]*primes[i];
                mn=min(mn,mi[i]);
            }
            for(int i=0;i<size;i++){
                if(mn==mi[i]) prime_num[i]++;
            }
            res.push_back(mn);
        }
        return res.back();
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.