/*
    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.
    
    Analysis:
    similar to ugly number 2, DP
    d[i] = Math.min(min, d[i-1]*primes[j])
    example:   6 [2,3,7] 
    2*[1],3*[1],7*[1] compare 2,3,7
    [1,2]->2*[2],3*[1,2],7*[1,2] compare [4,3,7]
    ....
    Time O(n*(primes.length))
*/

public class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] d = new int[n];
        d[0] = 1;
        int[] p = new int[primes.length];
        Arrays.fill(p,0);
        for(int i = 1; i < n; i++){
            int min = Integer.MAX_VALUE;
            for(int j = 0; j < primes.length; j++){
                min = Math.min(min,primes[j] * d[p[j]]) ;
            }
            d[i] = min;
            for(int k = 0; k < primes.length; k++){
                if(min == primes[k] * d[p[k]]){
                    p[k]++;
                }
            }
        }
        return d[n-1];
    }
}

@@ -1,14 +1,14 @@
 /*
+*
 %0A 
-  
+*
  Write a
@@ -51,20 +51,25 @@
 number.%0A
-%0A   
+ * %3Cp%3E%0A *
  Super u
@@ -174,16 +174,19 @@
 e k. For
+%0A *
  example
@@ -294,16 +294,19 @@
 n primes
+%0A *
  = %5B2, 7
@@ -331,23 +331,24 @@
 4.%0A 
-   %0A   
+* %3Cp%3E%0A *
  Note:%0A 
    (
@@ -343,18 +343,17 @@
  Note:%0A 
-  
+*
  (1) 1 i
@@ -397,18 +397,17 @@
 rimes.%0A 
-  
+*
  (2) The
@@ -456,18 +456,17 @@
 order.%0A 
-  
+*
  (3) 0 %3C
@@ -515,279 +515,207 @@
 0.%0A 
-   %0A    Analysis:%0A    similar to u
+* %3Cp%3E%0A * Tags: Math, Heap%0A * Similar Problems: (M) U
 gly 
-n
+N
 umber 
-2, DP%0A    d%5Bi%5D = Math.min(min, d%5Bi-1%5D*primes%5Bj%5D)%0A    example:   6 %5B2,3,7%5D %0A    2*%5B1%5D,3*%5B1%5D,7*%5B1%5D compare 2,3,7%0A    %5B1,2%5D-%3E2*%5B2%5D,3*%5B1,2%5D,7*%5B1,2%5D compare %5B4,3,7%5D%0A    ....%0A    Time O(n*(primes.length))%0A*/%0A%0Apublic class Solution %7B
+II%0A */%0A%0Apublic class SuperUglyNumber %7B%0A%0A    /**%0A     * Refer to ugly number 2%0A     * Use an array to keep all indices for primes%0A     */
 %0A   
@@ -783,43 +783,64 @@
  int
-%5B%5D d = new int%5Bn%5D;%0A        d%5B0%5D = 1
+ len = primes.length;%0A        int%5B%5D index = new int%5Blen%5D
 ;%0A  
@@ -851,17 +851,19 @@
   int%5B%5D 
-p
+res
  = new i
@@ -869,48 +869,30 @@
 int%5B
-primes.length%5D;%0A        Arrays.fill(p,0)
+n%5D;%0A        res%5B0%5D = 1
 ;%0A  
@@ -896,24 +896,25 @@
 %0A        for
+ 
 (int i = 1; 
@@ -924,16 +924,17 @@
  n; i++)
+ 
 %7B%0A      
@@ -979,24 +979,25 @@
          for
+ 
 (int j = 0; 
@@ -1004,27 +1004,18 @@
 j %3C 
-primes.length
+len
 ; j++)
+ 
 %7B%0A  
@@ -1047,33 +1047,39 @@
 min(
-min,primes
+res%5Bindex
 %5Bj%5D
+%5D
  * 
-d%5Bp%5Bj%5D%5D) 
+primes%5Bj%5D, min)
 ;%0A  
@@ -1102,17 +1102,19 @@
         
-d
+res
 %5Bi%5D = mi
@@ -1135,43 +1135,35 @@
  for
+ 
 (int 
-k
+j
  = 0; 
-k %3C primes.length; k
+j %3C len; j
 ++)
+ 
 %7B%0A  
@@ -1182,23 +1182,26 @@
   if
-(min ==
+ (res%5Bi%5D %25
  primes%5B
 k%5D *
@@ -1200,68 +1200,28 @@
 mes%5B
-k%5D * d%5Bp%5Bk%5D%5D)%7B%0A                    p%5Bk%5D++;%0A                %7D
+j%5D == 0) index%5Bj%5D++;
 %0A   
@@ -1260,12 +1260,16 @@
 urn 
-d%5Bn-
+res%5Bn - 
 1%5D;%0A

update super ugly number