Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
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.primes
are unique and sorted in ascending order.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;
}
}
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]
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];
}
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
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 >>