My 64 ms C++ solution beats 96.48% cppsubmissions

  • 0

    Improved from the solution by 'zjh08177 '( '7 line consice O(kn) c++ solution' in the discussion )

    vector 'index': with index[j] records the last location that multiplies primes[j].
    vector 'indexVal': with indexVal records ugly[index[j]]*primes[j].
    ugly[i] updates using the smallest number in the vector 'indexVal'.

     int nthSuperUglyNumber(int n, vector<int>& primes) {
            int primesL = primes.size();
            vector<int> index(primesL, 0), ugly(n, INT_MAX);
            int nextInx;
            vector<int> indexVal(primes);
            for(int i=1; i<n; i++){
                ugly[i] = indexVal[0];
                nextInx = 0;
                for(int j=1; j<primesL; j++){
                    if( indexVal[j] < ugly[i] ){
                        nextInx = j;
    				else if( indexVal[j] == ugly[i] ){
    					indexVal[j] = ugly[index[j]]*primes[j];
    			indexVal[nextInx] = ugly[index[nextInx]]*primes[nextInx];
            return ugly[n-1];

Log in to reply

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