algoadvance

You are given an array of integers primes and an integer n. A super ugly number is a positive integer whose prime factors are in the array primes. Return the nth super ugly number.

The nth super ugly number is guaranteed to fit in a 32-bit signed integer.

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

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.

Clarifying Questions

1. Can I assume that the array primes will always be non-empty and sorted?
2. Should the function return the nth super ugly number as an integer?

---

Strategy

1. Initialization: Use a min-heap (priority queue) to keep track of the current smallest super ugly number candidates.
2. Heap Operations: Initialize the heap with the first prime multiplied by 1 (the first super ugly number).
3. Generate Super Ugly Numbers: Use a loop to extract the smallest element from the heap, add new candidates by multiplying this smallest element with each prime, and push these new candidates back into the heap.
4. Avoid Duplicates: Use a set to keep track of numbers that have been added to the heap to avoid duplicates.
5. Stopping Condition: Repeat the above process until we’ve extracted n super ugly numbers.

---

Code

Here’s the implementation in Python:

import heapq

def nthSuperUglyNumber(n, primes):
    heap = [1]
    seen = {1}
    ugly = 1

    for _ in range(n):
        ugly = heapq.heappop(heap)
        for prime in primes:
            new_ugly = ugly * prime
            if new_ugly not in seen:
                seen.add(new_ugly)
                heapq.heappush(heap, new_ugly)

    return ugly

---

Time Complexity

• Heap Operations: Each insertion and extraction operation on the heap takes O(log m), where m is the size of the heap.
• Outer Loop: Runs n times.
• Inner Loop: Runs for each prime.

Hence, the overall time complexity is approximately O(n * k * log m), where:

• n is the target index.
• k is the number of primes.
• m is the number of elements in the heap, bounded by the number of unique products generated in the process.

This approach should be efficient enough given the constraints of the problem.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?