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:

Initialize a priority queue q with the number 1. This represents the first super ugly number.
Then, for producing the nth super ugly number, we perform a loop that runs n times.
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.
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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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:

Initialize the priority queue q with 1 (the first super ugly number).
For finding the 6th super ugly number, we need to iterate 6 times.
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

1import heapq  # Import the heapq module for heap operations
2
3class Solution:
4    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
5        # Initialize a min-heap with the first super ugly number, which is always 1
6        min_heap = [1]
7      
8        # Initialize a variable to store the current super ugly number
9        current_ugly_number = 0
10      
11        # Define the maximum value based on 32-bit signed integer range
12        max_value = (1 << 31) - 1
13      
14        # Iterate to find n super ugly numbers
15        for _ in range(n):
16            # Pop the smallest value from the min-heap
17            current_ugly_number = heapq.heappop(min_heap)
18          
19            # Try to generate new super ugly numbers by multiplying the current smallest
20            # with each of the provided prime factors
21            for prime in primes:
22                # Prevent integer overflow by ensuring the product does not exceed max_value
23                if current_ugly_number <= max_value // prime:
24                    heapq.heappush(min_heap, prime * current_ugly_number)
25              
26                # If the current ugly number is divisible by prime, 
27                # do not consider higher primes to avoid duplicates
28                if current_ugly_number % prime == 0:
29                    break
30                  
31        # Return the nth super ugly number after the loop ends
32        return current_ugly_number
33

1class Solution {
2    public int nthSuperUglyNumber(int n, int[] primes) {
3        // A min-heap to hold and automatically sort the ugly numbers
4        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
5        // Adding the first ugly number which is always 1
6        minHeap.offer(1);
7        // Variable to hold the current ugly number
8        int currentUglyNumber = 0;
9
10        // Generate the nth ugly number
11        while (n-- > 0) {
12            // Get the smallest ugly number from the min-heap
13            currentUglyNumber = minHeap.poll();
14
15            // Avoid duplicates by polling all instances of the current ugly number
16            while (!minHeap.isEmpty() && minHeap.peek() == currentUglyNumber) {
17                minHeap.poll();
18            }
19
20            // Multiply the current ugly number with each prime to get new ugly numbers
21            for (int prime : primes) {
22                // Check for overflow before adding the new ugly number
23                if (prime <= Integer.MAX_VALUE / currentUglyNumber) {
24                    minHeap.offer(prime * currentUglyNumber);
25                }
26                // If current ugly number is divisible by prime, no need to check further
27                if (currentUglyNumber % prime == 0) {
28                    break;
29                }
30            }
31        }
32        // Return the nth ugly number
33        return currentUglyNumber;
34    }
35}
36

1#include <vector>
2#include <queue>
3#include <climits>
4
5class Solution {
6public:
7    // Function to find the nth super ugly number
8    int nthSuperUglyNumber(int n, std::vector<int>& primes) {
9        // Priority queue to store intermediate super ugly numbers,
10        // with smaller numbers having higher priority.
11        std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
12
13        // Start with 1 as the first super ugly number.
14        minHeap.push(1);
15
16        int currentUglyNumber = 0; // Variable to store the current ugly number.
17
18        // Iterate until we find the nth super ugly number.
19        while (n--) {
20            // Extract the smallest super ugly number from the heap.
21            currentUglyNumber = minHeap.top();
22            minHeap.pop();
23
24            // Generate new super ugly numbers by multiplying with the given primes.
25            for (int prime : primes) {
26                // Prevent integer overflow by checking the multiplication condition.
27                if (currentUglyNumber <= INT_MAX / prime) {
28                    minHeap.push(prime * currentUglyNumber);
29                }
30
31                // If the current number is divisible by the prime, then break to
32                // avoid duplicates (since all primes could evenly divide the number).
33                if (currentUglyNumber % prime == 0) {
34                    break;
35                }
36            }
37        }
38        // Return the nth super ugly number.
39        return currentUglyNumber;
40    }
41};
42

1function nthSuperUglyNumber(n: number, primes: number[]): number {
2    // Array to store intermediate super ugly numbers,
3    // sorted so that smaller numbers come first.
4    let uglyNumbers: number[] = [1];
5
6    // Variable to store the index of the last number
7    // extracted from the sorted array for each prime.
8    let indices = new Array(primes.length).fill(0);
9
10    // Variable to store the next multiples for each prime.
11    let nextMultiples = [...primes];
12
13    for (let count = 1; count < n; count++) {
14        // Find the minimum super ugly number among the next multiples.
15        let nextUglyNumber = Math.min(...nextMultiples);
16
17        // Add the smallest number to the list of super ugly numbers.
18        uglyNumbers.push(nextUglyNumber);
19
20        // Update the multiples list and indices.
21        for (let j = 0; j < primes.length; j++) {
22            // If this prime's next multiple is the one we just added,
23            // update indices and calculate its new multiple.
24            if (nextMultiples[j] === nextUglyNumber) {
25                indices[j]++;
26                nextMultiples[j] = uglyNumbers[indices[j]] * primes[j];
27            }
28        }
29    }
30
31    // Return the nth super ugly number.
32    return uglyNumbers[n - 1];
33}
34

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Add another stack to store the minimums

Add a heap to store the minimums

Add a variable to track the minimum

Add a queue to store the minumums

I don't know