Coding Interview PatternsSuper Ugly Number
MediumK-way Merge
Super Ugly Number
Explanation & Solution
Description
A super ugly number is a positive integer whose prime factors are in the array primes.
Given an integer n and a sorted array of distinct primes primes, return the nth super ugly number. The 1st super ugly number is always 1.
Input:n = 12, primes = [2,7,13,19]
0
2
1
7
2
13
3
19
Output: 32
Explanation: The super ugly numbers are [1,2,4,7,8,13,14,16,19,26,28,32]. The 12th is 32.
Constraints
1 <= n <= 10^61 <= primes.length <= 152 <= primes[i] <= 100primes[i]is guaranteed to be prime.- All values of
primesare unique and sorted in ascending order.
Approach
K-way Merge pattern
1. Initialize the DP Table and Pointers
dp[0] = 1— the first super ugly number is always 1- Create a pointer
ptrs[j]for each prime, initialized to 0 - Each pointer tracks which dp value to multiply
primes[j]by next
2. Generate Numbers One at a Time
- For each position
ifrom 1 to n-1, compute the candidate for each prime:dp[ptrs[j]] * primes[j] - The next super ugly number is the minimum of all candidates
3. Advance Pointers That Produced the Minimum
- After recording
dp[i], increment every pointerjwheredp[ptrs[j]] * primes[j] === dp[i] - Advancing all tied pointers prevents duplicates (e.g. 2×3 and 3×2 both equal 6)
4. Return the nth Value
- After filling all n entries,
dp[n-1]is the answer
Key Insight
- This is a k-way merge of virtual sorted sequences
primes[j] × dp[0], primes[j] × dp[1], ...— each pointer independently walks one such sequence and the minimum across all pointers is the next value
Time
O(n × k) where k is the number of primesSpace
O(n + k)