Quite intuitive solution accepted with 40ms in C, well-explained


  • 0

    Since the first SuperUgly is 1 and the rest are primes and the combinations of primes in sequence. To find the nth SuperUgly, we have to find all that are less: 1st, 2nd, 3rd, ..., n-1th using the combination of 1 and primes. But if we combine every two one from (1, primes) the other from (1, primes, ...., ith) then compare them to find the next bigger one, the time cost will k*n at least. To reduce the time complexity, we are about to use

    an array to track the index for each prime (index pointing to the smallest SuperUgly that prime can get)

    and then we can find the next bigger one in O(k) time cost, just traversing all primes and calculate

    uglies[index[j]]*primes[j] -> each prime will have a correlated index, check?

    • first, before we get started all index should be pointed to zero - the 1 - the first SuperUgly;
    • second, to find the next bigger one, we have to traverse the primes and get the smallest one using the index;
    • third, after retrieving the next bigger one, we have to move the all the replicated SuperUgly index to the next SuperUgly for next round -> we should isolate all duplicates, right?

    Bang. So quick! End of story.

    • Space cost O(n+k)
    • Time cost O(nk)

    //AC - 40ms;
    int nthSuperUglyNumber(int n, int* primes, int size)
    {
        int *uglies = (int*)malloc(sizeof(int)*n);
        uglies[0] = 1; //the first SuperUgly;
        int *indexes = (int*)malloc(sizeof(int)*size);
        memset(indexes, 0, sizeof(int)*size); //all pointing to the first SuperUgly first;
        for(int i = 1; i < n; i++) //you will never know how big n can be;
            uglies[i] = INT_MAX;
        for(int i = 1; i < n; i++)
        {
            for(int j = 0; j < size; j++) //search for the smallest that can be retrieved from primes and former SuperUgly numbers;
            {
                int t = uglies[indexes[j]]*primes[j];
                if(uglies[i] < t)
                    uglies[i] = t;
            }
            for(int j = 0; j < size; j++) //make sure there will be no duplicate, so that we can find the (i+1)th;
                indexes[j] += (uglies[i]==uglies[indexes[j]]*primes[j]);
        }
        return uglies[n-1];
    }

Log in to reply
 

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