313. Super Ugly Number

Posted on Edited on In

313. Super Ugly Number

Description

Difficulty: Medium

Related Topics: Array, Math, Dynamic Programming

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.

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 <= 105
  • 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.

Hints/Notes

  • priority queue

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        priority_queue<vector<long>, vector<vector<long>>, greater<vector<long>>> pq;
        vector<long> res;
        for (int prime : primes) {
            pq.push({1, 0, prime});
        }
        while (res.size() < n) {
            long val = pq.top()[0];
            res.push_back(val);
            while (pq.top()[0] == val) {
                int idx = pq.top()[1];
                int prime = pq.top()[2];
                pq.pop();
                pq.push({res[idx] * prime, idx + 1, prime});
            }
        }
        return res.back();
    }
};