A super ugly number is a positive integer whose prime factors are in the array primes.
Given an integer n and an array of integers primes, return the nth super ugly number.
The nth super ugly number is guaranteed to fit in a 32-bit signed integer.
Example 1:
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].
Example 2:
Input: n = 1, primes = [2,3,5] Output: 1 Explanation: 1 has no prime factors, therefore all of its prime factors are in the array primes = [2,3,5].
Constraints:
1 <= n <= 1051 <= primes.length <= 1002 <= primes[i] <= 1000primes[i] is guaranteed to be a prime number.primes are unique and sorted in ascending order.Problem Overview: You need the nth super ugly number. A super ugly number is a positive integer whose prime factors belong only to a given list primes. The sequence starts from 1. The task is essentially generating numbers in sorted order while restricting their prime factors.
Approach 1: Dynamic Programming Using Merge List (O(n * k) time, O(n + k) space)
This approach builds the sequence incrementally using dynamic programming. Maintain an array dp where dp[i] stores the i-th super ugly number. For each prime in primes, track an index pointing to the position in dp whose value should be multiplied by that prime next. At each step, compute candidates like dp[index[j]] * primes[j], pick the minimum, and append it to the sequence. If multiple primes generate the same value, increment all corresponding indices to avoid duplicates. This works like merging k sorted lists of multiples and guarantees the numbers remain sorted.
Approach 2: Heap-Based Approach (O(n log k) time, O(n + k) space)
A min-heap keeps track of the next candidate numbers generated from each prime. Start with 1 in the result list. Push tuples representing the next value for each prime into a heap. Each heap element stores the value, the prime, and the index in the generated sequence. Pop the smallest value, append it to the result if it is new, then push the next multiple for that prime using the next index. The heap always exposes the smallest candidate, so the sequence remains sorted. This method resembles merging sorted streams and works well when the number of primes is large.
The problem mixes ideas from math and sequence generation. The key challenge is preventing duplicates while keeping numbers sorted without generating all integers and factorizing them.
Recommended for interviews: The dynamic programming merge-list method is the expected solution. It runs in O(n * k) time and avoids heap overhead while clearly demonstrating how multiple sorted sequences are merged. Explaining the pointer updates and duplicate handling shows strong understanding. The heap approach is also valid and often easier to implement conceptually, but interviewers typically prefer the DP pointer technique for its deterministic behavior and lower constant factors.
This approach uses dynamic programming with the strategy of merging lists, each generated by multiplying the super ugly numbers with each of the given primes.
The solution involves creating an array, `ugly`, to store the n super ugly numbers. An `idx` array keeps the index of the current multiplier for each prime, and `values` holds the next candidate super ugly number for each prime. The main loop continues until the nth super ugly number is found by choosing the minimum from `values`, then updating each `values[j]` by multiplying the next number from `ugly` indexed by `idx[j]` with its corresponding prime.
Time Complexity: O(n * primesSize)
Space Complexity: O(n + primesSize)
The heap-based approach optimizes the time complexity by using a min-heap to keep track of the next smallest super ugly number among all potential candidates generated by multiplying primes with existing super ugly numbers.
This C implementation uses a custom min-heap via an array of structs, each representing the current state of a specific prime's contribution to the super ugly numbers. The heap is maintained and used to efficiently get the next smallest product among all primes by keeping track of their indices and values across iterations.
Time Complexity: O(n log(primesSize))
Space Complexity: O(n + primesSize)
We use a priority queue (min heap) to maintain all possible super ugly numbers, initially putting 1 into the queue.
Each time we take the smallest super ugly number x from the queue, multiply x by each number in the array primes, and put the product into the queue. Repeat the above operation n times to get the nth super ugly number.
Since the problem guarantees that the nth super ugly number is within the range of a 32-bit signed integer, before we put the product into the queue, we can first check whether the product exceeds 2^{31} - 1. If it does, there is no need to put the product into the queue. In addition, the Euler sieve can be used for optimization.
The time complexity is O(n times m times log (n times m)), and the space complexity is O(n times m). Where m and n are the length of the array primes and the given integer n respectively.
Go
| Approach | Complexity |
|---|---|
| Dynamic Programming Using Merge List | Time Complexity: O(n * primesSize) |
| Heap-Based Approach | Time Complexity: O(n log(primesSize)) |
| Priority Queue (Min Heap) | — |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming Using Merge List | O(n * k) | O(n + k) | Best general solution. Deterministic generation using multiple pointers. |
| Heap-Based Approach | O(n log k) | O(n + k) | Useful when modeling the problem as merging sorted streams with a priority queue. |
Super Ugly Numbers | Dynamic Programming | Leetcode 313 • Pepcoding • 13,368 views views
Watch 9 more video solutions →Practice Super Ugly Number with our built-in code editor and test cases.
Practice on FleetCode