Super Ugly Number solution and explanation
Deloitte
Google
9 more videos on this problem
Super Ugly Numbers | Dynamic Programming | Leetcode 313Pepcoding · 35:02 · 13K views
Leetcode 313 Super Ugly NumberRen Zhang · 27:52 · 3K views
Ugly Number | Super Ugly Number | Whiteboard explanation | Leetcode #263 #313Binod Suman Academy · 23:41 · 2K views
Super Ugly Numbers | dynamic programming | Leetcode#313Joey'sTech · 23:27 · 2K views
Super Ugly Number [ Dynamic Programming ]nETSETOS · 25:28 · 1K views
LeetCode 313 | Super Ugly Numberleetuition · 19:48 · 1K views
【每日一题】313. Super Ugly Number, 6/25/2021Huifeng Guan · 16:46 · 1K views
Super Ugly Number Leetcode Problem | Medium Difficulty problem | Heap Problem | Interview ProblemKnow Your Algorithms · 8:26 · 1K views
Day 60/90 |⚡🚀 🔥 313. Super Ugly Number Made Easy 🚀 | Brute Force to Min Heap! 🔥 | K-Way MergeCTO Bhaiya · 1:10:31 · 560 views
Leetcode Question 313 "Super Ugly Number" in JavaGhumman Tech · 11:56 · 183 views
The problem
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.- All the values of
primesare 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.
def nthSuperUglyNumber(n, primes):
size = len(primes)
ugly = [0] * n
idx = [0] * size
values = primes[:]
ugly[0] = 1
for i in range(1, n):
next_ugly = min(values)
ugly[i] = next_ugly
for j in range(size):
if values[j] == next_ugly:
idx[j] += 1
values[j] = ugly[idx[j]] * primes[j]
return ugly[-1]import java.util.Arrays;
public class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
int[] ugly = new int[n];
int[] idx = new int[primes.length];
int[] values = Arrays.copyOf(primes, primes.length);
ugly[0] = 1;
for (int i = 1; i < n; i++) {
int nextUgly = values[0];
for (int primeValue : values) {
nextUgly = Math.min(nextUgly, primeValue);
}
ugly[i] = nextUgly;
for (int j = 0; j < values.length; j++) {
if (values[j] == nextUgly) {
values[j] = ugly[++idx[j]] * primes[j];
}
}
}
return ugly[n - 1];
}
}#include <vector>
#include <algorithm>
using namespace std;
int nthSuperUglyNumber(int n, vector<int>& primes) {
vector<int> dp(n, INT_MAX), idx(primes.size(), 0), values(primes);
dp[0] = 1;
for (int i = 1; i < n; ++i) {
for (const auto value : values) {
dp[i] = min(dp[i], value);
}
for (int j = 0; j < primes.size(); ++j) {
if (values[j] == dp[i]) {
values[j] = dp[++idx[j]] * primes[j];
}
}
}
return dp[n - 1];
}var nthSuperUglyNumber = function(n, primes) {
const ugly = Array(n).fill(0);
const idx = Array(primes.length).fill(0);
const values = primes.slice();
ugly[0] = 1;
for (let i = 1; i < n; i++) {
let nextUgly = Math.min(...values);
ugly[i] = nextUgly;
for (let j = 0; j < primes.length; j++) {
if (values[j] === nextUgly) {
values[j] = ugly[++idx[j]] * primes[j];
}
}
}
return ugly[n - 1];
};#include <stdlib.h>
int nthSuperUglyNumber(int n, int* primes, int primesSize) {
int* ugly = (int*)malloc(n * sizeof(int));
int* idx = (int*)calloc(primesSize, sizeof(int));
int* values = (int*)malloc(primesSize * sizeof(int));
ugly[0] = 1;
for (int i = 0; i < primesSize; ++i) {
values[i] = primes[i];
}
for (int i = 1; i < n; ++i) {
int next_ugly = values[0];
for (int j = 1; j < primesSize; ++j) {
if (values[j] < next_ugly) {
next_ugly = values[j];
}
}
ugly[i] = next_ugly;
for (int j = 0; j < primesSize; ++j) {
if (values[j] == next_ugly) {
values[j] = ugly[++idx[j]] * primes[j];
}
}
}
int result = ugly[n - 1];
free(ugly);
free(idx);
free(values);
return result;
}using System;
public class Solution {
public int NthSuperUglyNumber(int n, int[] primes) {
var ugly = new int[n];
var idx = new int[primes.Length];
var values = new int[primes.Length];
Array.Copy(primes, values, primes.Length);
ugly[0] = 1;
for (int i = 1; i < n; i++) {
int nextUgly = values[0];
foreach (var value in values) {
if (value < nextUgly) nextUgly = value;
}
ugly[i] = nextUgly;
for (int j = 0; j < primes.Length; j++) {
if (values[j] == nextUgly) {
values[j] = ugly[++idx[j]] * primes[j];
}
}
}
return ugly[n - 1];
}
}The Python implementation uses lists to track the `ugly` numbers, the indices `idx` for each prime, and the `values` list initially set to the primes. It repeatedly finds the smallest next potential ugly number and updates it by moving the prime's `idx` position ahead until the nth super ugly number is produced.
Time Complexity: O(n * len(primes))
Space Complexity: O(n + len(primes))
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.
import heapq
def nthSuperUglyNumber(n, primes):
h = [1]
seen = {1}
for _ in range(n-1):
current = heapq.heappop(h)
for prime in primes:
newUgly = current * prime
if newUgly not in seen:
seen.add(newUgly)
heapq.heappush(h, newUgly)
return heapq.heappop(h)import java.util.PriorityQueue;
import java.util.Set;
import java.util.HashSet;
public class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
Set<Long> set = new HashSet<>();
PriorityQueue<Long> pq = new PriorityQueue<>();
pq.add(1L);
set.add(1L);
while (--n > 0) {
long current = pq.poll();
for (int prime : primes) {
long next = current * prime;
if (set.add(next)) {
pq.add(next);
}
}
}
return pq.peek().intValue();
}
}#include <vector>
#include <queue>
#include <set>
using namespace std;
class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
set<long> s;
priority_queue<long, vector<long>, greater<>> pq;
pq.push(1);
s.insert(1);
while (--n) {
long curr = pq.top(); pq.pop();
for (long prime : primes) {
long next = curr * prime;
if (s.insert(next).second) {
pq.push(next);
}
}
}
return pq.top();
}
};var nthSuperUglyNumber = function(n, primes) {
const heap = new MinPriorityQueue();
const set = new Set();
heap.enqueue(1);
set.add(1);
while (--n > 0) {
const curr = heap.dequeue().element;
for (const prime of primes) {
const next = curr * prime;
if (!set.has(next)) {
set.add(next);
heap.enqueue(next);
}
}
}
return heap.dequeue().element;
};#include <stdio.h>
#include <stdlib.h>
typedef struct {
int idx;
int prime;
long value;
} HeapNode;
int compare(const void *a, const void *b) {
return ((HeapNode *)a)->value > ((HeapNode *)b)->value ? 1 : -1;
}
void heapify_down(HeapNode *heap, int heapSize, int i) {
int smallest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < heapSize && compare(&heap[left], &heap[smallest]) < 0)
smallest = left;
if (right < heapSize && compare(&heap[right], &heap[smallest]) < 0)
smallest = right;
if (smallest != i) {
HeapNode temp = heap[i];
heap[i] = heap[smallest];
heap[smallest] = temp;
heapify_down(heap, heapSize, smallest);
}
}
int nthSuperUglyNumber(int n, int *primes, int primesSize) {
int *ugly = (int *)malloc(n * sizeof(int));
HeapNode *heap = (HeapNode *)malloc(primesSize * sizeof(HeapNode));
ugly[0] = 1;
for (int i = 0; i < primesSize; ++i) {
heap[i] = (HeapNode){1, primes[i], (long)primes[i]};
}
for (int i = 1; i < n; ++i) {
ugly[i] = heap[0].value;
while (heap[0].value == ugly[i]) {
heap[0].value = (long)ugly[heap[0].idx++] * heap[0].prime;
heapify_down(heap, primesSize, 0);
}
}
int result = ugly[n - 1];
free(ugly);
free(heap);
return result;
}using System;
using System.Collections;
using System.Collections.Generic;
public class Solution {
public int NthSuperUglyNumber(int n, int[] primes) {
var heap = new SortedSet<long>();
heap.Add(1L);
long current = 1;
for (int i = 0; i < n; i++) {
current = heap.Min;
heap.Remove(current);
foreach (var prime in primes) {
heap.Add(current * prime);
}
}
return (int)current;
}
}This Python solution employs a heap (priority queue) and set-based uniqueness check. A list `h` (heap storage) models the core heap, explicitly ordering values to promptly extract new super ugly numbers and retain progressive states through iterations.
Time Complexity: O(n log k)
Space Complexity: O(n + k)
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.
func nthSuperUglyNumber(n int, primes []int) (x int) {
q := hp{[]int{1}}
for n > 0 {
n--
x = heap.Pop(&q).(int)
for _, k := range primes {
if x <= math.MaxInt32/k {
heap.Push(&q, k*x)
}
if x%k == 0 {
break
}
}
}
return
}
type hp struct{ sort.IntSlice }
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
a := h.IntSlice
v := a[len(a)-1]
h.IntSlice = a[:len(a)-1]
return v
}Approach 4: Default Approach
type Ugly struct{ value, prime, index int }
type Queue []Ugly
func (u Queue) Len() int { return len(u) }
func (u Queue) Swap(i, j int) { u[i], u[j] = u[j], u[i] }
func (u Queue) Less(i, j int) bool { return u[i].value < u[j].value }
func (u *Queue) Push(v any) { *u = append(*u, v.(Ugly)) }
func (u *Queue) Pop() any {
old, x := *u, (*u)[len(*u)-1]
*u = old[:len(old)-1]
return x
}
func nthSuperUglyNumber(n int, primes []int) int {
ugly, pq, p := make([]int, n+1), &Queue{}, 2
ugly[1] = 1
heap.Init(pq)
for _, v := range primes {
heap.Push(pq, Ugly{value: v, prime: v, index: 2})
}
for p <= n {
top := heap.Pop(pq).(Ugly)
if ugly[p-1] != top.value {
ugly[p], p = top.value, p+1
}
top.value, top.index = ugly[top.index]*top.prime, top.index+1
heap.Push(pq, top)
}
return ugly[n]
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Using Merge List | Time Complexity: O(n * len(primes)) |
| Heap-Based Approach | Time Complexity: O(n log k) |
| Priority Queue (Min Heap) | – |
| Default Approach | – |
Complexity analysis
| 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. |
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.