304 North Cardinal St.
Dorchester Center, MA 02124

# Super Ugly Number LeetCode Solution

## Problem – Super Ugly Number LeetCode Solution

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.

## Super Ugly Number LeetCode Solution in Java

``````lic int nthSuperUglyNumberHeap(int n, int[] primes) {
int[] ugly = new int[n];

PriorityQueue<Num> pq = new PriorityQueue<>();
for (int i = 0; i < primes.length; i++) pq.add(new Num(primes[i], 1, primes[i]));
ugly[0] = 1;

for (int i = 1; i < n; i++) {
ugly[i] = pq.peek().val;
while (pq.peek().val == ugly[i]) {
Num nxt = pq.poll();
pq.add(new Num(nxt.p * ugly[nxt.idx], nxt.idx + 1, nxt.p));
}
}

return ugly[n - 1];
}

private class Num implements Comparable<Num> {
int val;
int idx;
int p;

public Num(int val, int idx, int p) {
this.val = val;
this.idx = idx;
this.p = p;
}

@Override
public int compareTo(Num that) {
return this.val - that.val;
}
}``````

## Super Ugly Number LeetCode Solution in Python

``````class Solution(object):
def nthSuperUglyNumber(self, n, primes):
size = len(primes)
ugly, dp, index, ugly_nums = 1, [1], [0] * size, [1] * size
for i in range(1, n):
# compute possibly ugly numbers and update index
for j in range(0, size):
if ugly_nums[j] == ugly:
ugly_nums[j] = dp[index[j]] * primes[j]
index[j] += 1
# get the minimum
ugly = min(ugly_nums)
dp.append(ugly)
return dp[-1]
``````

## Super Ugly Number LeetCode Solution in C++

``````int nthSuperUglyNumber(int n, vector<int>& primes) {
vector<int> index(primes.size(), 0), ugly(n, INT_MAX);
ugly[0]=1;
for(int i=1; i<n; i++){
for(int j=0; j<primes.size(); j++) ugly[i]=min(ugly[i],ugly[index[j]]*primes[j]);
for(int j=0; j<primes.size(); j++) index[j]+=(ugly[i]==ugly[index[j]]*primes[j]);
}
return ugly[n-1];
}
``````
##### Super Ugly Number LeetCode Solution Review:

In our experience, we suggest you solve this Super Ugly Number LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Super Ugly Number LeetCode Solution

Find on Leetcode

##### Conclusion:

I hope this Super Ugly Number LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions