# 313. Super Ugly Number

## 1. Question

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.

## 2. Examples

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].


## 3. Constraints

• 1 <= n <= 106
• 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.

## 5. Solutions

class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
HashSet<Long> added = new HashSet<>();
PriorityQueue<Long> queue = new PriorityQueue<>();
queue.offer(1L);
int ugly = 0;

for (int i = 0; i < n; i++) {
Long curr = queue.poll();
ugly = Math.toIntExact(curr);
for (int prime : primes) {
long next = curr * prime;
queue.offer(next);
}
}

}
return ugly;
}
}