# Simple addiction logic to reduce the runtime. 28ms and beats 99.77%

• ``````public class Solution {
//this solution is developed by the idea of the following article: http://www.geeksforgeeks.org/ugly-numbers/
//I did a very sample improvement to reduce the run-time.
//The improvement is to return the current minimum value of the new generated ugly number and the index to the
//prime number which generates the new ugly number.
//Now we can update the index array base on the return index of the prime number.

public int nthSuperUglyNumber(int n, int[] primes) {
if(n==0 || primes==null || primes.length==0){
return 0;
}

int[] res = new int[n]; //hold the result
res[0]=1; //first result is always 1

int primeSize = primes.length;
int[] index = new int[primeSize]; //index point to the value in "res".
//It will use to generate the ugly number
int[] values = new int[primeSize]; //hold the new generated ugly numbers

//now fill up the result array
for(int i=1; i<n; i++){
//calculate ugly numbers and store them into values array
for(int j=0; j<primeSize; j++){
values[j]=res[index[j]]*primes[j];
}

//find the min and insert to the result;
Pair minPair = getMin(values);
res[i]=minPair.value;
//update the index. this is the simple trick to reduce the run-time
for(int j=minPair.index; j<primeSize; j++){
if(minPair.value == values[j]){
index[j]++;
}
}

}

return res[n-1];
}

//find the minimum ugly numbers in the new generated ugly numbers list
private Pair getMin(int[] values ){
int res = Integer.MAX_VALUE;
int index=0;
for(int i=0; i<values.length; i++){
if(values[i]<res){
res=values[i];
index=i;
}
}
return new Pair(index, res);
}

//private class to hold the minimum values and the index to the prime number
private class Pair{
protected int index;
protected int value;

public Pair(int index, int value){
this.index=index;
this.value=value;
}
}
``````

}

• Interesting, I implement your core improvement in my CPP code, but runtime have no change. it's still 100ms and 90.62%. May be it is because you use C and my CPP code have the extra cost when using vectors?

``````int nthSuperUglyNumber(int n, vector<int>& primes) {
int sz = primes.size();
vector<int> idxs(sz, 1);
vector<int> v(n + 1);v[1] = 1;
vector<int> tmps(sz);
for (int i = 2;i <= n;i++) {
int m = INT_MAX; int minj = INT_MAX;
for (int j = 0;j < sz;j++) {
tmps[j] = v[idxs[j]] * primes[j];
if (tmps[j] < m) {
m = tmps[j];
v[i] = m; minj = j;
}
}

for (int j = minj;j < sz;j++) {
if (m == tmps[j]) {
idxs[j] = idxs[j] + 1;
}
}
}
return v[n];
}``````

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