313. Super Ugly Number

Problem Description

A super ugly number is defined as a positive integer where all of its prime factors are part of a given list of prime numbers. The problem asks for the nth super ugly number, given n and a list of these prime factors, which are in an array called primes.

More concretely, you need to generate super ugly numbers in ascending order and then return the number that is in the nth position in this sequence.

For example, if primes = [2, 7, 13, 19], the sequence of super ugly numbers starts as 1, 2, 4, 7, 8, 13, 14, 16, 19, ..., and so on. In this sequence, 1 is always included and is considered the first super ugly number.

An important constraint is that the nth super ugly number is guaranteed to fit in a 32-bit signed integer. This means the result should be less than or equal to 2^31 - 1.

Intuition

The intuition for solving this problem relies on building the sequence of super ugly numbers one by one, efficiently. The method used to keep the sequence sorted and avoid duplicates is a priority queue, commonly implemented with a heap in many programming languages.

The key insight is that every new super ugly number can be formed by multiplying a previously found super ugly number with one of the prime factors from the given primes array. This process will ensure we're covering all possible combinations while maintaining the sequence sorted.

As we're interested only in the nth super ugly number, we can use a min-heap (a priority queue that pops the smallest element) to repeatedly extract the smallest super ugly number and generate its successors by multiplying with the prime factors. This way, we ensure that numbers are always processed in increasing order, relating back to the constraint that we're required to return the nth super ugly number.

To further optimize and avoid duplicate calculations, when we take the smallest number from the heap, only the first prime factor that produces a new super ugly number which hasn't been added to the heap before will generate successors for this number. This is made possible by checking if the current super ugly number is divisible by a prime factor. If it is, it means we have found it using this prime factor previously, thus we can safely stop checking later prime factors for this iteration.

Additionally, there's a check to ensure we do not exceed the 32-bit integer limit during our multiplication, which aligns with the constraint mentioned in the problem description.

Learn more about Math and Dynamic Programming patterns.

Solution Approach

The solution uses a priority queue data structure for maintaining the order of super ugly numbers. In Python, a priority queue can be implemented using a heap, from the heapq module.

Here's a step-by-step walkthrough of the implementation process:

1. Initialize a priority queue q with the number 1. This represents the first super ugly number.
2. Then, for producing the nth super ugly number, we perform a loop that runs n times.
3. In each iteration of the loop:
   • We pop the smallest number x from the heap. This is the next super ugly number in sequence.
   • For each prime factor k in the primes array:
     • We multiply x by k and check if this product would exceed the maximum 32-bit signed integer value (which is (1 << 31) - 1 in the code). If not, we push the product onto the heap.
     • If x is divisible by k, we stop looping through the prime factors for this x, as we have found the smallest prime factor that can generate x, and we want to avoid duplicates in the heap.
   • The check for the maximum value is to prevent integer overflows, and the condition x % k == 0 is to ensure we do not insert the same super ugly number into the heap more than once.
4. After running the loop n times, the nth super ugly number x is the last number popped from the heap.

The usage of the heap is crucial here, as it allows us to efficiently get the smallest number, which is our next super ugly number in each iteration. Also, the heap manages possible duplicates, which would otherwise complicate the implementation if we used another data structure such as an array or list.

Overall, this approach is efficient because it only considers necessary multiples of super ugly numbers and prime factors, and due to the nature of heap operations, the time complexity for each insertion and extraction is O(log n), making the overall algorithm significantly faster than a brute-force method that might consider all possible products.

Example Walkthrough

Let’s walk through a small example to illustrate the solution approach. Consider finding the 6th super ugly number with primes = [2, 3, 5].

Step-by-step process:

1. Initialize the priority queue q with 1 (the first super ugly number).
2. For finding the 6th super ugly number, we need to iterate 6 times.
3. Begin the loop:
   • First iteration:
     Pop the smallest number from the heap, which is 1. Multiply it by each of the primes.
     • Multiply by 2: Get 2, push onto the heap.
     • Multiply by 3: Get 3, push onto the heap.
     • Multiply by 5: Get 5, push onto the heap. Heap after first iteration: [2, 3, 5]
   • Second iteration:
     Pop the smallest number, which is 2.
     • Multiply by 2: Get 4, push onto the heap.
     • 2 is not divisible by the next prime 3, so we continue.
     • Multiply by 3: Get 6, push onto the heap.
     • Multiply by 5: Get 10, push onto the heap. Heap after second iteration: [3, 4, 5, 6, 10]
   • Third iteration: Pop the smallest number, which is 3.
     • Multiply by 2: Get 6, which is already in the heap, so we skip pushing it.
     • 3 is divisible by 3, we can stop here. Heap after third iteration: [4, 5, 6, 10]
   • Fourth iteration: Pop the smallest number, which is 4.
     • Multiply by 2: Get 8, push onto the heap.
     • 4 is not divisible by the next prime 3, so we continue.
     • Multiply by 3: Get 12, push onto the heap.
     • Multiply by 5: Get 20, push onto the heap. Heap after fourth iteration: [5, 6, 8, 10, 12, 20]
   • Fifth iteration: Pop the smallest number, which is 5.
     • Multiply by 2: Get 10, which is already in the heap, so we skip pushing it.
     • 5 is not divisible by the next prime 3, so we continue.
     • Multiply by 3: Get 15, push onto the heap.
     • Multiply by 5: Get 25, push onto the heap. Heap after fifth iteration: [6, 8, 10, 12, 15, 20, 25]
   • Sixth iteration: Pop the smallest number, which is 6.
     • Multiply by 2: Get 12, which is already in the heap, so we skip pushing it.
     • 6 is divisible by 3, so we can stop here.

At this point, we have popped 6 numbers, which means the last popped number, 6, is our answer. The 6th super ugly number is 6.

By following this heap-based approach and ensuring we only push new products onto the heap, we can efficiently find the desired super ugly number without duplicate calculations or unnecessary multiplications.

Solution Implementation

Time and Space Complexity

The provided code defines a function to find the n-th super ugly number where super ugly numbers are positive integers whose prime factors are in the given list of primes.

Time Complexity

The time complexity of the code is as follows:

• The for loop runs n times because we are looking for the n-th super ugly number.
• Inside the loop, the heappop() operation is performed once, which has a complexity of O(log m) (where m is the current size of the heap q).
• After popping the smallest element, we iterate over the list of primes, which has a complexity of O(k) per loop iteration, where k is the number of primes.
• In the worst case, we push one element to the heap per every prime in the list, resulting in O(k log m) since each heappush() operation has a complexity of O(log m).
• The if x % k == 0: break will potentially reduce the number of pushes since it stops pushing once the prime divides x since x wouldn't be super ugly for some larger prime factors.
• The multiplication k * x is O(1) operation, and the comparison x <= mx // k is also O(1).

Given that the heap potentially has all n elements and the number of primes is k, the overall time complexity is O(n * k * log(n)).

Space Complexity

The space complexity is as follows:

• The heap q can grow up to a size of n, holding at most all the super ugly numbers up to the n-th.
• No additional meaningful storage is used, so the space complexity is primarily from the heap.

Thus, the space complexity is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.