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 ++;
        }
        return top;
    }
};




Related Posts

K-Th Smallest Prime Fraction Problem

LeetCode 786. You are given a sorted integer array arr...

Course Schedule III Problem

LeetCode 630. There are n different online courses numbered from...

IPO Problem

LeetCode 502. Suppose LeetCode will start its IPO soon. In...

Sliding Window Median Problem

LeetCode 480. The median is the middle value in an...

Relative Ranks Problem

LeetCode 506. You are given an integer array score of...

Ugly Number II Problem

LeetCode 264. An ugly number is a positive integer whose...