A super ugly number is a positive integer whose every prime factor appears in the prime array primes.

Given an integer n and an integer array primes, return the n-th super ugly number.

The input guarantees that the n-th super ugly number is within the range of a signed 32-bit integer.

Example 1:

Input:n = 12, primes = [2,7,13,19]
Output:32
Explanation:Given the prime array of length 4, primes = [2,7,13,19], the first 12 super ugly numbers are: [1,2,4,7,8,13,14,16,19,26,28,32].

Example 2:

Input:n = 1, primes = [2,3,5]
Output:1
Explanation:1 has no prime factors, so all of its prime factors are in the prime array primes = [2,3,5].

Approach

#

The problem is relatively straightforward: we need to generate a list containing all super ugly numbers, and we only care about the n-th one.

There are several ways to build this list. A common approach uses a priority queue.

A priority queue is a special data structure that keeps all of its elements ordered. We can therefore maintain a priority queue whose initial value is [1], and perform the following operations n times:

    1.在第n次的时候，从优先队列中取出一个最小的数字t
    2.t即为第n个超级丑数
    3.将t * primes[0], t * primes[1], .....等数字放入优先队列中。
    4.这样就能保证所有超级丑数都曾经被加入过该优先队列，而且因为我们是按照从小到大的顺序取的，所以第二条成立

Following this approach, we can compute the n-th super ugly number in \(O(n * primes.length * log_2(n * primes.length))\) time.

Rust Code

#

use std::collections::*;
# struct Solution;
impl Solution {
    pub fn nth_super_ugly_number(mut n: i32, primes: Vec<i32>) -> i32 {
        let mut set = BTreeSet::new();
        set.insert(1);
        while set.len() > 0 {
            let first = *set.iter().next().unwrap();
            set.remove(&first);
            for &prime in &primes {
                if (first as i64) * (prime as i64) < (i32::MAX as i64) {
                    set.insert(first * prime);
                }
            }
            n -= 1;
            if n == 0 {
                return first;
            }
        }
        0
    }
}

An Advanced Method

#

Approach

#

It is not difficult to see that every term in the super ugly number sequence can be represented as the product of a number in primes and a super ugly number that appeared earlier.

After understanding the previous method, we can also see that at every step we take out a super ugly number, multiply it by a number in primes, and put the result back into the super ugly number sequence as a candidate.

However, this produces many redundant and unnecessary calculations. For example, the sequence of super ugly numbers may be very long even though we only need its first few terms. This motivates us to find a new way to calculate it.

We therefore create a new array called pointer. Each of its entries corresponds to one entry in primes, and all entries initially equal 0. We also need to record the ugly numbers in a sequence named dp.

In each iteration, perform the following steps:

1.计算出当前最小候选超级丑数的值
2.具体的流程为求 dp[pointer[i]] * primes[i] 的最小值(i的取值范围就是primes的长度m)
3.该数即为下一个超级丑数 dp_nxt
4.对于所有项 dp[pointer[i]] * primes[i] == dp_nxt 的i，均使 pointer[i] 增加1

To review the idea, every super ugly number can be obtained by multiplying a previously seen super ugly number by a number in primes. The current pointer indicates the position of that earlier super ugly number.

Duplicates can occur. For example, 2*9 and 6*3 both produce 18, which is why pointer must be advanced for every entry that equals the minimum value.

With this traversal, we can enumerate every possible super ugly number in ascending order while avoiding many invalid calculations. Following this approach, all calculations can be completed in O(n * primes.length) time.

use std::collections::*;
# struct Solution;
impl Solution {
    pub fn nth_super_ugly_number(n: i32, primes: Vec<i32>) -> i32 {
        let mut dp = vec![1];
        let n = n as usize;
        let m = primes.len();
        let mut pointer = vec![0; m];
        while dp.len() < n {
            let mut min_pos = 0;
            for i in 1..m {
                if dp[pointer[i]] * primes[i] < dp[pointer[min_pos]] * primes[min_pos] {
                    min_pos = i;
                }
            }
            let tmp = dp[pointer[min_pos]] * primes[min_pos];
            dp.push(tmp);
            for i in 0..m {
                if dp[pointer[i]] * primes[i] == tmp {
                    pointer[i] += 1;
                }
            }
        }
        println!("{:?}", dp);
        dp[n - 1]
    }
}