# 313. 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: 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 ≤ 106, 0 < primes[i] < 1000.
- The nth super ugly number is guaranteed to fit in a 32-bit signed integer.
# Solution
Approach 1: Minimum heap.
# Code (Python)
Approach 1:
# Code (C++)
Approach 1:
class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
priority_queue<long, vector<long>, greater<long>> minHeap;
minHeap.push(1);
long num;
for (int i = 0; i < n; ++i)
{
num = minHeap.top();
while (!minHeap.empty() && minHeap.top() == num)
minHeap.pop();
for (int j = 0; j < primes.size(); ++j)
minHeap.push(num * primes[j]);
}
return num;
}
};
class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
int k = primes.size();
if (n == 0 || k == 0)
return 0;
int ugly[n+1];
ugly[0] = 0;
ugly[1] = 1;
vector<int> idx(k, 1);
for (int i = 2; i <= n; ++i) {
int min = INT_MAX;
for (int j = 0; j < k; ++j) {
if (ugly[idx[j]] * primes[j] == ugly[i-1])
idx[j]++;
min = std::min(min, ugly[idx[j]] * primes[j]);
}
ugly[i] = min;
}
return ugly[n];
}
};