# Super Ugly Number Problem

## Description

LeetCode Problem 313.

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 n^th super ugly number.

The n^th super ugly number is guaranteed to fit in a 32-bit signed integer.

Example 1:

``````1
2
3
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:

``````1
2
3
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 <= 10^6
• 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.

## Sample C++ Code

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
priority_queue<long long int, vector<long long int>, greater<long long int>> pq;
pq.push(1);

int idx = 0;
long long int top;
while (idx < n) {
top = pq.top();

for (int i = 0; i < primes.size(); i ++)
pq.push(top*primes[i]);

while (!pq.empty() && pq.top() == top)
pq.pop();

idx ++;
}
}
};
``````