Skip to main content
Talentd

Super Ugly Number - Solution & Explanation

MediumArrayMathDynamic Programming17 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

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 <= 105
  • 1 <= primes.length <= 100
  • 2 <= primes[i] <= 1000
  • primes[i] is guaranteed to be a prime number.
  • All the values of primes are unique and sorted in ascending order.

Approach Overview

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.

Approach 1: Dynamic Programming Using Merge List

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * primesSize)
Space Complexity: O(n + primesSize)

Try this approach in the editor →

Approach 2: Heap-Based Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log(primesSize))
Space Complexity: O(n + primesSize)

Try this approach in the editor →

Approach 3: Priority Queue (Min Heap)

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.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Approach 4: Default Approach

Code

Go

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Using Merge List

Time Complexity: O(n * primesSize)
Space Complexity: O(n + primesSize)

Heap-Based Approach

Time Complexity: O(n log(primesSize))
Space Complexity: O(n + primesSize)

Priority Queue (Min Heap)—
Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming Using Merge ListO(n * k)O(n + k)Best general solution. Deterministic generation using multiple pointers.
Heap-Based ApproachO(n log k)O(n + k)Useful when modeling the problem as merging sorted streams with a priority queue.

Video Solution

Super Ugly Numbers | Dynamic Programming | Leetcode 313 • Pepcoding • 13,703 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Super Ugly Number easy or hard?
Super Ugly Number is considered a medium difficulty problem. The challenge lies in efficiently generating numbers in sorted order without duplicates while handling multiple prime factors. Understanding the multi-pointer dynamic programming pattern is the key insight.
Super Ugly Number Python/Java solution
Most solutions in Python or Java follow the DP pointer approach. Maintain an array dp where dp[i] is the i-th super ugly number and track indices for each prime. At every step compute the minimum candidate multiple, append it, and advance the corresponding indices to avoid duplicates.
How to solve Super Ugly Number in O(n)?
Strict O(n) time is not achievable because each generated number must be compared against candidates from multiple primes. The closest practical solution is the dynamic programming pointer method with O(n * k) time. It efficiently merges k sorted sequences of prime multiples.
What is the best approach for Super Ugly Number?
The dynamic programming merge-list approach is typically the best solution. It maintains pointers for each prime and generates the next smallest super ugly number by comparing candidate multiples. The algorithm runs in O(n * k) time where k is the number of primes, and avoids duplicates by advancing all pointers that produce the same value.
Is Super Ugly Number asked at Google/Amazon/Meta?
Super Ugly Number is a known dynamic programming and sequence-generation problem similar to Ugly Number II. Variants of this pattern appear in interviews at large tech companies such as Google, Amazon, and Microsoft, especially when testing DP and heap fundamentals.
What data structure is used in Super Ugly Number?
Two common structures are used: a dynamic programming array to store generated ugly numbers and multiple pointer indices for each prime. Some implementations use a min-heap (priority queue) to always extract the next smallest candidate value.
What is the time complexity of Super Ugly Number?
The common optimal solution using dynamic programming runs in O(n * k) time and O(n + k) space, where n is the target index and k is the number of primes. A heap-based implementation can achieve O(n log k) time by always extracting the smallest candidate from a priority queue.

Ready to solve this problem?

Practice Super Ugly Number with our built-in code editor and test cases.

Practice on FleetCode
Previous

Ugly Number II