1
// ---------------------O(nlogk)-------------------------
2

3
class Solution {
4
  public int nthSuperUglyNumber(int n, int[] primes) {
5
    int[] dp = new int[n + 1];
6
    dp[1] = 1;
7

8
    PriorityQueue<Pair> pq = new PriorityQueue<>();
9

10
    for (int i = 0; i < primes.length; i++) {
11
      pq.add(new Pair(primes[i], 1, primes[i]));
12
    }
13

14
    for (int i = 2; i <= n; ) {
15
      Pair curr = pq.remove();
16

17
      if (curr.val != dp[i - 1]) {
18
        dp[i] = curr.val;
19
        i++;
20
      }
21

22
      int newval = curr.prime * dp[curr.ptr + 1];
23
      if (newval > 0) {
24
        pq.add(new Pair(curr.prime, curr.ptr + 1, newval));
25
      }
26
    }
27

28
    return dp[n];
29
  }
30
}
31

32
class Pair implements Comparable<Pair> {
33
  int prime;
34
  int ptr;
35
  int val;
36

37
  public Pair(int prime, int ptr, int val) {
38
    this.prime = prime;
39
    this.ptr = ptr;
40
    this.val = val;
41
  }
42

43
  public int compareTo(Pair o) {
44
    return this.val - o.val;
45
  }
46
}
47

48
// -----------------------O(nk)---------------------------
49

50
// class Solution {
51
//     public int nthSuperUglyNumber(int n, int[] primes) {
52
//         int []dp=new int[n+1];
53
//         dp[1]=1;
54

55
//         int []ptr=new int[primes.length];
56

57
//         Arrays.fill(ptr,1);
58

59
//         for(int i=2;i<=n;i++){
60

61
//             int min=Integer.MAX_VALUE;
62

63
//             for(int j=0;j<ptr.length;j++){
64
//                 int val=dp[ptr[j]]*primes[j];
65
//                 if(val>0){
66
//                     min=Math.min(min,val);
67
//                 }
68

69
//             }
70

71
//             dp[i]=min;
72

73
//             for(int j=0;j<ptr.length;j++){
74
//                 int val=dp[ptr[j]]*primes[j];
75
//                 if(val>0 && min==val){
76
//                     ptr[j]++;
77
//                 }
78
//             }
79
//         }
80

81
//         return dp[n];
82
//     }
83
// }