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.
// 36ms, 93%
class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
vector<int> idx(primes.size(), 0);
vector<int> nums(n);
nums[0] = 1;
for (int i = 1; i < n; i++) {
int minV = INT_MAX, vi;
for (int j = 0; j < primes.size(); j++) {
int t = primes[j] * nums[idx[j]]; // 2 * nums[i2], 3 * nums[i3]
if (t < minV) {
minV = t;
vi = j;
}
}
nums[i] = minV;
for (int j = 0; j < primes.size(); j++) {
int t = primes[j] * nums[idx[j]];
if (t == minV) {
idx[j]++;
}
}
}
return nums.back();
}
};