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 n
th 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 n
th 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 n
th 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 n
th 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 n
th 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
n
th super ugly number, we perform a loop that runsn
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 theprimes
array:- We multiply
x
byk
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 byk
, we stop looping through the prime factors for thisx
, as we have found the smallest prime factor that can generatex
, and we want to avoid duplicates in the heap.
- We multiply
- 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.
- We pop the smallest number
- After running the loop
n
times, then
th super ugly numberx
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 EvaluatorExample 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.
- First iteration:
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 runsn
times because we are looking for then
-th super ugly number. - Inside the loop, the
heappop()
operation is performed once, which has a complexity ofO(log m)
(wherem
is the current size of the heapq
). - After popping the smallest element, we iterate over the list of
primes
, which has a complexity ofO(k)
per loop iteration, wherek
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 eachheappush()
operation has a complexity ofO(log m)
. - The
if x % k == 0: break
will potentially reduce the number of pushes since it stops pushing once the prime dividesx
sincex
wouldn't be super ugly for some larger prime factors. - The multiplication
k * x
isO(1)
operation, and the comparisonx <= mx // k
is alsoO(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 ofn
, holding at most all the super ugly numbers up to then
-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.
Which of the following array represent a max heap?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!