## Algorithm

Problem Name: 313. Super Ugly Number

A super ugly number is a positive integer whose prime factors are in the array `primes`.

Given an integer `n` and an array of integers `primes`, return the `nth` super ugly number.

The `nth` super ugly number is guaranteed to fit in a 32-bit signed integer.

Example 1:

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

Example 2:

```Input: n = 1, primes = [2,3,5]
Output: 1
Explanation: 1 has no prime factors, therefore all of its prime factors are in the array primes = [2,3,5].
```

Constraints:

• `1 <= n <= 105`
• `1 <= primes.length <= 100`
• `2 <= primes[i] <= 1000`
• `primes[i]` is guaranteed to be a prime number.
• All the values of `primes` are unique and sorted in ascending order.

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
int nthSuperUglyNumber(int n, vector& primes) {
vectordp(n);
dp[0] = 1;
vectorp(primes.size());
for(int i = 1; i < n; i++){
dp[i] = INT_MAX;
for(int j = 0; j < p.size(); j++) dp[i] = min(dp[i], dp[p[j]] * primes[j]);
for(int j = 0; j < p.size(); j++) if(dp[p[j]] * primes[j] == dp[i]) p[j]++;
}
return dp[n - 1];
}
};
``````
Copy The Code &

Input

cmd
n = 12, primes = [2,7,13,19]

Output

cmd
32

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public static int nthSuperUglyNumber(int n, int[] primes) {
int[] arr = new int[n+1];
arr[0] = 1;

int[] counter = new int[primes.length];

for (int i=1; i``````
``` Copy The Code & Input x – + cmd n = 12, primes = [2,7,13,19] Output x – + cmd 32 ```
``` #3 Code Example with Javascript Programming Code - Javascript Programming const nthSuperUglyNumber = function(n, primes) { if (n === 1) return 1 const indexes = new Array(primes.length).fill(0) const arr = [1] for (let i = 1; i <= n - 1; i++) { arr[i] = +Infinity for (let j = 0; j < primes.length; j++) { arr[i] = Math.min(arr[i], arr[indexes[j]] * primes[j]) } for (let j = 0; j < primes.length; j++) { if (arr[i] === arr[indexes[j]] * primes[j]) { indexes[j]++ } } } return arr[n - 1] } Copy The Code & Input x – + cmd n = 1, primes = [2,3,5] Output x – + cmd 1 #4 Code Example with Python Programming Code - Python Programming class Solution: def nthSuperUglyNumber(self, n, primes): arr, heap, used = [1], primes[:], set() for i in range(1, n): num = heapq.heappop(heap) arr.append(num) for p in primes: if p * num not in used: heapq.heappush(heap, p * num) used.add(p * num) return arr[-1] Copy The Code & Input x – + cmd n = 1, primes = [2,3,5] Output x – + cmd 1 Demonstration ```
``` #312 Leetcode Burst Balloons Solution in C, C++, Java, JavaScript, Python, C# Leetcode #315 Leetcode Count of Smaller Numbers After Self Solution in C, C++, Java, JavaScript, Python, C# Leetcode ```
``` ```