Problem Description

A super ugly number is a positive integer whose only prime factors come from a given array primes.

Given an integer n and an array of integers primes, you need to find the nth super ugly number in the sequence.

For example, if primes = [2, 3, 5], the sequence of super ugly numbers would be: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ... because:

• 1 has no prime factors
• 2 = 2 (prime factor: 2)
• 3 = 3 (prime factor: 3)
• 4 = 2 × 2 (prime factor: 2)
• 5 = 5 (prime factor: 5)
• 6 = 2 × 3 (prime factors: 2, 3)
• 8 = 2 × 2 × 2 (prime factor: 2)
• And so on...

The number 7 would not be in this sequence because 7 is a prime number not in the primes array.

The problem guarantees that the nth super ugly number will fit within a 32-bit signed integer (won't exceed 2^31 - 1).

Intuition

To generate super ugly numbers, we need to think about how they're formed. Every super ugly number (except 1) is created by multiplying a smaller super ugly number by one of the primes in our array.

Starting with 1, we can generate new super ugly numbers by multiplying it with each prime: 1 × 2, 1 × 3, 1 × 5, etc. Then from these results, we can generate even more by multiplying them with the primes again.

The key insight is that we need to generate these numbers in sorted order to find the nth one. A min heap is perfect for this - it always gives us the smallest unprocessed number. We start with 1 in the heap, then repeatedly:

1. Extract the smallest number x from the heap
2. Multiply x by each prime to generate new candidates
3. Add these new candidates to the heap

However, this approach would generate duplicates. For instance, 6 could be generated as both 2 × 3 and 3 × 2. To avoid duplicates, we use a clever optimization: when we extract a number x, we only multiply it by primes that are greater than or equal to its smallest prime factor. This is achieved by breaking the loop when x % prime == 0 - if x is divisible by a prime, we know that prime is its smallest prime factor, so we don't need to multiply by larger primes (they would create duplicates later).

The overflow check x <= mx // k ensures we don't exceed the 32-bit integer limit when computing k * x.

After extracting exactly n numbers from the heap, the last extracted number is our answer - the nth super ugly number.

Solution Approach

The solution uses a min heap (priority queue) to generate super ugly numbers in ascending order.

Implementation Steps:

1. Initialize the heap: Create a min heap q and add the first super ugly number 1 to it.

2. Set up variables:

   • x = 0 to store the current super ugly number being processed
   • mx = (1 << 31) - 1 which equals 2^31 - 1, the maximum value for a 32-bit signed integer

3. Generate n super ugly numbers: Loop n times, and in each iteration:

   a. Extract minimum: Pop the smallest number from the heap using heappop(q) and store it in x. This is guaranteed to be the next super ugly number in sequence.

   b. Generate new candidates: For each prime k in the primes array:

   • Overflow check: Before multiplying, verify that x <= mx // k to ensure k * x won't overflow
   • Add to heap: If no overflow, push k * x into the heap as a new candidate
   • Duplicate prevention: If x % k == 0, it means k is the smallest prime factor of x. Break the loop to avoid generating duplicates (this implements the Euler sieve optimization)

4. Return result: After n iterations, x contains the nth super ugly number.

Why the duplicate prevention works: When x is divisible by prime k, we know that x = k × y for some smaller super ugly number y. If we continued with larger primes p > k, we'd generate x × p = k × y × p. But this same number will be generated later as y × p × k when we process y × p. By breaking early, we ensure each super ugly number is generated exactly once, following a canonical ordering where we multiply by primes in non-decreasing order.

Time Complexity: O(n × m × log(nm)) where m is the size of the primes array, since we perform up to n × m heap operations, each taking O(log(heap_size)) time.

Space Complexity: O(n × m) for storing the heap, which can grow up to this size in the worst case.

Example Walkthrough

Let's walk through finding the 4th super ugly number with primes = [2, 3, 5].

Initial Setup:

• Heap: [1]
• n = 4 (we need to extract 4 numbers)
• mx = 2^31 - 1 (overflow limit)

Iteration 1 (n=1):

• Extract minimum: x = 1 (heap becomes empty)
• Generate new candidates from x = 1:
  • For prime 2: Check 1 <= mx // 2 ✓, add 1 × 2 = 2 to heap
  • For prime 3: Check 1 <= mx // 3 ✓, add 1 × 3 = 3 to heap
  • For prime 5: Check 1 <= mx // 5 ✓, add 1 × 5 = 5 to heap
• Heap after iteration: [2, 3, 5]
• 1st super ugly number: 1

Iteration 2 (n=2):

• Extract minimum: x = 2 (heap becomes [3, 5])
• Generate new candidates from x = 2:
  • For prime 2: Check 2 <= mx // 2 ✓, add 2 × 2 = 4 to heap
  • Check 2 % 2 == 0 ✓, so break (avoid duplicates)
• Heap after iteration: [3, 5, 4] → [3, 4, 5] (after heapify)
• 2nd super ugly number: 2

Iteration 3 (n=3):

• Extract minimum: x = 3 (heap becomes [4, 5])
• Generate new candidates from x = 3:
  • For prime 2: Check 3 <= mx // 2 ✓, add 3 × 2 = 6 to heap
  • For prime 3: Check 3 <= mx // 3 ✓, add 3 × 3 = 9 to heap
  • Check 3 % 3 == 0 ✓, so break (avoid duplicates)
• Heap after iteration: [4, 5, 6, 9]
• 3rd super ugly number: 3

Iteration 4 (n=4):

• Extract minimum: x = 4 (heap becomes [5, 6, 9])
• Generate new candidates from x = 4:
  • For prime 2: Check 4 <= mx // 2 ✓, add 4 × 2 = 8 to heap
  • Check 4 % 2 == 0 ✓, so break (avoid duplicates)
• Heap after iteration: [5, 6, 9, 8] → [5, 6, 8, 9] (after heapify)
• 4th super ugly number: 4

Result: The 4th super ugly number is 4.

Why duplicate prevention works: Notice when we extracted 4, we only multiplied by 2 and stopped. If we had continued and multiplied 4 by 3 to get 12, this would be a duplicate because 12 will also be generated as 6 × 2 when we process 6 later. By breaking when x % prime == 0, we ensure each number is generated exactly once through a canonical path where we multiply by primes in non-decreasing order.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × m × log(n × m))

The algorithm uses a min-heap to generate the nth super ugly number. For each of the n iterations:

• We perform one heappop operation: O(log(heap_size))
• We iterate through all m primes, and for each prime that doesn't cause early termination, we perform a heappush operation: O(log(heap_size))
• In the worst case, we push all m primes into the heap for each number generated

The heap size can grow up to O(n × m) in the worst case, as we might push m elements per iteration and pop only 1. Therefore, each heap operation costs O(log(n × m)).

Since we perform n iterations, and each iteration involves up to m heap push operations plus one pop operation, the total time complexity is O(n × m × log(n × m)).

Space Complexity: O(n × m)

The space is dominated by the heap q. In the worst-case scenario, the heap can contain up to O(n × m) elements. This happens when we continuously add new numbers to the heap faster than we remove them. Since we add up to m numbers per iteration and remove only 1, after n iterations, the heap size can be bounded by O(n × m).

Common Pitfalls

1. Duplicate Generation Without Proper Prevention

The most critical pitfall is generating duplicate super ugly numbers in the heap, which leads to incorrect results and inefficiency.

Problem Example: Without the if current_ugly % prime == 0: break optimization, consider primes = [2, 3] and current_ugly = 6:

• When processing 6, we'd generate 6 × 2 = 12 and 6 × 3 = 18
• Later, when processing 4, we'd generate 4 × 3 = 12 (duplicate!)
• This creates duplicates in our sequence

Solution: The break statement ensures we only multiply by primes in a canonical order. When current_ugly is divisible by a prime, we stop there because any larger prime multiplication will be handled when we process the factored-out version later.

2. Integer Overflow

Without the overflow check if current_ugly <= max_value // prime, multiplying large super ugly numbers with primes could cause integer overflow, leading to negative numbers or wrapped values in the heap.

Problem Example: If current_ugly = 1,500,000,000 and prime = 3, then current_ugly × prime = 4,500,000,000 which exceeds 2^31 - 1.

Solution: Always verify current_ugly <= max_value // prime before multiplication. This ensures the product stays within the 32-bit signed integer range.

3. Using a Set Instead of Heap Optimization

A naive approach might use a set to track seen numbers to avoid duplicates:

seen = set()
if prime * current_ugly not in seen:
    heapq.heappush(min_heap, prime * current_ugly)
    seen.add(prime * current_ugly)

Problem: This uses O(n × m) extra space for the set and makes operations slower due to set lookups.

Solution: The break optimization elegantly prevents duplicates without extra space by ensuring each number is generated through exactly one path (its canonical factorization order).

4. Not Understanding Why the Break Works

Developers might remove the break thinking it's just an optimization, not realizing it's essential for correctness.

Key Insight: The break ensures we only generate multiples using the "leftmost" prime factor path. For example, 12 = 2² × 3 is only generated as 4 × 3, never as 6 × 2, because when we process 6 = 2 × 3, we break at prime 2.