> For the complete documentation index, see [llms.txt](https://aaronice.gitbook.io/lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aaronice.gitbook.io/lintcode/mathematics/super-ugly-number.md).

# Super Ugly Number

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`.

**Example:**

Input:

```
Input: n = 12, primes = [2,7,13,19]
Output: 32 
Explanation: [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`  is a super ugly number for any given `primes`.
* The given numbers in `primes` are in ascending order.
* 0  < `k` ≤ 100, 0  < `n` ≤ 10^6 , 0  < `primes[i]` <  1000.
* The n th super ugly number is guaranteed to fit in a 32-bit signed integer.

## Analysis

Very similar to Ugly Number II problem.

See reference: [https://leetcode.com/problems/super-ugly-number/discuss/76291/Java-three-methods-23ms-36-ms-58ms(with-heap)-performance-explained](https://leetcode.com/problems/super-ugly-number/discuss/76291/Java-three-methods-23ms-36-ms-58ms%28with-heap%29-performance-explained)

## Solution

Heap - (193 ms AC 13.61%)

```java
class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        pq.offer(1);
        for (int prime : primes) {
            pq.offer(prime);
        }
        for (int i = 1; i < n; i++) {
            int tmp = pq.poll();
            while (!pq.isEmpty() && pq.peek() == tmp) {
                tmp = pq.poll();
            }
            for (int prime : primes) {
                long multiply = (long) tmp * (long) prime;
                if (multiply < Integer.MAX_VALUE) {
                    pq.offer((int) multiply); 
                }
            }
        }
        return pq.poll().intValue();
    }
}
```

DP (9ms 100% AC)

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

DP 2

```java
class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] ugly = new int[n];
        int k = primes.length;
        ugly[0] = 1;
        int[] it = new int[k];
        int[] nxt = new int[k];
        for(int j=0;j<k;j++) {
            nxt[j] = primes[j];
        }        
        for(int i=1;i<n;i++) {
            int nxt_ugly = Integer.MAX_VALUE;
            for(int j = 0;j<k;j++) {
                nxt_ugly = Math.min(nxt_ugly, nxt[j]);
            }            
            ugly[i] = nxt_ugly;
            for(int j = 0;j<k;j++) {
                if(nxt[j] == nxt_ugly) {
                    it[j]++;
                    nxt[j] = ugly[it[j]]*primes[j];
                }                
            }                         
        }
        return ugly[n-1];
    }
}
```