Super Ugly Number

07/17/2016 Math Heap

Question

Write a program to find the nth super ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [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] of size 4.

Note:

  1. 1 is a super ugly number for any given primes.
  2. The given numbers in primes are in ascending order.
  3. 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.

CPP Heap Solution

Result: Accepted Time: 24 ms

Here should be some explanations.


int data[1000000+5]={1},cnt;
int value[105],ptr[105];
int nth(int n, int* primes, int primesSize) {
    int ptr[105]={0}, value[105];
    int min_value, last = 1, cnt = 1;
    memcpy(value,primes,sizeof(int)*primesSize);
    while(cnt < n)
    {
        min_value = INT_MAX;
        for(int i = 0; i < primesSize; i++)
        {
            if(value[i] <= last)
                value[i] = primes[i] * data[++ptr[i]];
            if(min_value > value[i])
                min_value = value[i];
        }
        data[cnt++] = last = min_value;
    }
    return data[n-1];
}
class Solution {
public:
    struct cmp{
        bool operator() (const int &a,const int &b) const{ return value[a] > value[b];}
    };
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        
        for(int i = 0; i < primes.size(); i++)
            value[i] = primes[i];
        if(primes.size()*n < 8000480)
            return nth(n,value,primes.size());
        priority_queue<int,vector<int>,cmp> que;
        cnt = 1;
         for(int i = 0; i < primes.size(); i++)
                que.push(i),ptr[i] = 0;
        for(int i = 0; i < n; i++)
        {
            int tmp = que.top();que.pop();
            if(value[tmp] != data[cnt -1])
                data[cnt++] = value[tmp];
            else
                i--;
            value[tmp] = primes[tmp]*data[++ptr[tmp]];
            que.push(tmp);
        }
        return data[n-1];
    }
};

Complexity Analytics

  • Time Complexity:
  • Space Complexity:

C Solution

Result: Accepted Time: 20 ms

#define MAXN (1000000+5)
int data[MAXN]={1};
int nthSuperUglyNumber(int n, int* primes, int primesSize) {
    int ptr[105]={0}, value[105];
    int min_value, last = 1, cnt = 1;
    memcpy(value,primes,sizeof(int)*primesSize);
    while(cnt < n)
    {
        min_value = INT_MAX;
        for(int i = 0; i < primesSize; i++)
        {
            if(value[i] <= last)
                value[i] = primes[i] * data[++ptr[i]];
            if(min_value > value[i])
                min_value = value[i];
        }
        data[cnt++] = last = min_value;
    }
    return data[n-1];
}

Complexity Analytics

  • Time Complexity:
  • Space Complexity: