> 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];
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/mathematics/super-ugly-number.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.