# 112ms C++ solution with explanation

• ``````class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
vector<int> superUglyNumbers;
superUglyNumbers.push_back(1);  // first super ugly number
int numPrimes = primes.size();
vector<int> idxs(numPrimes, 0);
// add super ugly number up to nth
while(superUglyNumbers.size() < n)
{
int nextSuperUglyNumber = superUglyNumbers[idxs[0]]*primes[0];   // next super ugly number
for(int i = 0; i < numPrimes; i++)
{
nextSuperUglyNumber = min(nextSuperUglyNumber, superUglyNumbers[idxs[i]]*primes[i]);
}
for(int i = 0; i < numPrimes; i++)
{
if(nextSuperUglyNumber == superUglyNumbers[idxs[i]]*primes[i])
{
idxs[i]++;
}
}
superUglyNumbers.push_back(nextSuperUglyNumber);
}

return superUglyNumbers[n-1];
}
};``````

• #32ms C solution

``````#define MAXN (1000000+5)
int data[MAXN];

int nthSuperUglyNumber(int n, int* primes, int primesSize) {
int ptr[105]={0};
int value[105];
int min_value;
int cnt = 1;
data[0] = 1;
for(int i=0;i<primesSize;i++)
value[i] = primes[i];
while(cnt <= n)
{
min_value = 0x7fffffff;
for(int i=0; i< primesSize;i++)
if(min_value > value[i])
min_value = value[i];
data[cnt++] = min_value;
for(int i = 0; i < primesSize;i++)
if(value[i] == min_value)
{
value[i] = primes[i] * data[++ptr[i]];
if(value[i] <= 0)
value[i] = 0x7fffffff;
}

}
return data[n-1];
}``````

• C style is so fast

• Could it be optimized to avoid the second 'for loop'? Maybe by updating the value[i] on the first loop if value[i] == min_value, because that would mean that there is a duplicate and is ok to advance.

What do you think?

• Yeah,it's faster!20ms.

``````#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];
}``````

• Actually,using heap will be faster! The complexity will be O(n*log(primesSize)),However ,using priority queue in C++ is slower! Maybe to implement it myself is a good way.

• @AllenYick
I have tried to copy/paste your code but failed. It seems your initial value after while loop should be
"
int nextSuperUglyNumber = INT_MAX;
"

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