algoadvance

Leetcode 313. Super Ugly Number

Problem Statement

You are given an array of integers primes, and an integer n. The n-th super ugly number is defined as the smallest positive integer that can be expressed as a product of any combination of the numbers in primes. The sequence starts with 1 as the first super ugly number.

Write a function that returns the n-th super ugly number.

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

Clarifying Questions

  1. Negative values in primes array: Should we consider any negative values or zeros in the primes array?
    • No, primes array will contain positive integers only.
  2. Maximum value of n and primes array length: What are the constraints for n and the length of the primes array?
    • Each integer in primes is guaranteed to be greater than 1, and the length of primes is at most 100. The value of n does not exceed 100,000.

Strategy

To generate the sequence of super ugly numbers, we can use a min-heap (priority queue) for efficiently finding the next super ugly number. Here’s the step-by-step approach:

  1. Initialize a List: Start with a list containing only the first super ugly number, which is 1.

  2. Use a Min-Heap: Utilize a min-heap to dynamically get the smallest super ugly number not already in the list.

  3. Heap Elements: Each element in the heap will be a tuple of the form (next_ugly, prime, index), where next_ugly is the current product, prime is the prime number used to obtain next_ugly, and index is the position in the list of super ugly numbers that generated next_ugly.

  4. Generate and Track Super Ugly Numbers: Extract the smallest element from the heap, add it to the list if it is not already present, and insert the next potential product of the prime indexed at index + 1.

  5. Repeat Until nth Super Ugly Number: Continue the above process until n super ugly numbers are generated.

Time Complexity

The time complexity is O(n log k), where n is the number of super ugly numbers we want to generate, and k is the number of primes. The primary operations involve heap insertions and extractions, which take log k time.

Code

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>

using namespace std;

int nthSuperUglyNumber(int n, vector<int>& primes) {
    vector<long> uglyNumbers(n);
    uglyNumbers[0] = 1;
    auto compare = [](pair<long, pair<int, int>>& a, pair<long, pair<int, int>>& b) {
        return a.first > b.first;
    };
    priority_queue<pair<long, pair<int, int>>, vector<pair<long, pair<int, int>>>, decltype(compare)> minHeap(compare);
    
    for (int prime : primes) {
        minHeap.push({prime, { prime, 0 } });
    }
    
    for (int i = 1; i < n; ++i) {
        uglyNumbers[i] = minHeap.top().first;
        
        while (minHeap.top().first == uglyNumbers[i]) {
            auto current = minHeap.top();
            minHeap.pop();
            long next_ugly = current.first;
            int prime = current.second.first;
            int index = current.second.second;
            
            minHeap.push({ prime * uglyNumbers[index + 1], { prime, index + 1 } });
        }
    }
    
    return uglyNumbers[n - 1];
}

int main() {
    vector<int> primes = {2, 7, 13, 19};
    int n = 12;
    cout << nthSuperUglyNumber(n, primes) << endl; // Output: 32
}

Explanation

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI