# 313. Super Ugly Number

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2FpRcqqP2CmEDZZK3eiNFC%2Fimage.png?alt=media\&token=dfd8bb5e-dc51-433a-8bda-a2f30f14a886)

```
k 個 primes * dp[x] 取最小 (pq)so, poll -> logk
做 n 次, set to result
so t is...

T: O(nlogk)
```

````java
```java
class Solution {
    class Value {
        int product;
        int prime;
        int index;
        Value (int product, int prime, int index){
            this.product = product;
            this.prime = prime;
            this.index = index;
        }
    }
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] dp = new int[n];
        Queue<Value> pq = new PriorityQueue<>((a, b) -> a.product - b.product);
        for (int i = 0; i < primes.length; i++) {
            pq.offer(new Value(1, primes[i], 0)); // put 0 start index for each prime list index
        }

        int idx = 0; // start index
        while (!pq.isEmpty() && idx < n) {
            Value cur = pq.poll();
            int product = cur.product;
            int prime = cur.prime;
            int index = cur.index;
            if (idx == 0 || product != dp[idx-1]) { // idx == 0, direct set the product
                dp[idx++] = product; // when product is unique, we set it (filter duplicated product)
            }
            // so we can put all generated number into pq, even some are duplicated
            pq.offer(new Value(dp[index]*prime, prime, index+1));
            
        }
        return dp[n-1];
    }
}

/**
pq
to find min number add to int ugly[n]

pq (product, prime, index)

prime: [2,7,13,19]
index is what we use current from ugly[index]

if product == ugly[p] -> filter duplicated product, so it's fine to continuesly add new number to pq'
skip, pq.poll()
at mean we also offer new value to pq, 

T: O(nlogk)
we always k primes in PQ
and we ask for n th, so it's nlogk'
 */
```
````
