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

## Rust Solution

``````struct Solution;
use std::cmp::Reverse;
use std::collections::BinaryHeap;
use std::collections::HashSet;

impl Solution {
fn nth_super_ugly_number(mut n: i32, primes: Vec<i32>) -> i32 {
let mut queue: BinaryHeap<Reverse<i32>> = BinaryHeap::new();
let mut visited: HashSet<i32> = HashSet::new();
queue.push(Reverse(1));
while n > 1 {
let min = queue.pop().unwrap().0;
for &x in &primes {
if let Some(y) = x.checked_mul(min) {
if visited.insert(y) {
queue.push(Reverse(y));
}
}
}
n -= 1;
}
queue.pop().unwrap().0
}
}

#[test]
fn test() {
let n = 12;
let primes = vec![2, 7, 13, 19];
let res = 32;
assert_eq!(Solution::nth_super_ugly_number(n, primes), res);
}
``````

Having problems with this solution? Click here to submit an issue on github.