Wednesday, August 9, 2017

Super Ugly number

The idea is from Ugly Number II.
https://leetcode.com/problems/ugly-number-ii/
Below code is for ugly number II
public int nthUglyNumber(int n){
 int i2=0, i3=0, i5=0;
 int[] k = new int[n];
 k[0] = 1;
 for (int i=1; i<n; i++) {
  k[i] = Math.min(k[i2]*2, Math.min(k[i3]*3, k[i5]*5));
  if (k[i]%2 == 0) i2++;
  if (k[i]%3 == 0) i3++;
  if (k[i]%5 == 0) i5++;
 }
 
 return k[n-1];
}
Similarly, for this problem, just use loop to replace above i2, i3, i5.
public int nthSuperUglyNumber(int n, int[] primes) {
    int len = primes.length;
    int[] index = new int[len]; //index[0]==0, ... index[len-1]==0
    int[] res = new int[n];
    res[0] = 1;
    for(int i=1; i<n; i++) {
        int min = Integer.MAX_VALUE;
        for(int j=0; j<len; j++){
            min = Math.min(res[index[j]]*primes[j], min);
        }
        res[i] = min;
        for (int j=0; j<len; j++) {
            if(res[i]%primes[j]==0) index[j]++;
        }

    }
    
    return res[n-1];
}

No comments:

Post a Comment