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<int>& primes) {
vector<int>dp(n);
dp[0] = 1;
vector<int>p(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 < n; i++) {
int temp = Integer.MAX_VALUE;
int idx = -1;

for (int j=0; j < primes.length; j++) {
if (primes[j]*arr[counter[j]] < temp) {
temp = primes[j]*arr[counter[j]];
idx = j;
}
else if (primes[j]*arr[counter[j]] == temp) {
counter[j]++;
}
}

arr[i] = temp;
counter[idx]++;
}

return arr[n-1];
}
}
``````
Copy The Code &

Input

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

Output

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

cmd
n = 1, primes = [2,3,5]

Output

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)
return arr[-1]
``````
Copy The Code &

Input

cmd
n = 1, primes = [2,3,5]

Output

cmd
1