Super Ugly Number — Solution in Python, Java & C++
Super Ugly Number solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Super Ugly Number is a medium coding problem on dynamic programming, math and heap, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Dynamic Programming, Math, Heap
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A super ugly number is a positive integer whose prime factors all appear in the given list primes. By convention 1 is the first super ugly number.
Return the n-th super ugly number.
Example 1
Input: n = 12, primes = [2,7,13,19]
Output: 32
Explanation: The sequence starts 1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32.
Example 2
Input: n = 1, primes = [2,3,5]
Output: 1
Explanation: 1 is always first.
Example 3
Input: n = 5, primes = [3]
Output: 81
Explanation: Powers of 3: 1, 3, 9, 27, 81.
Constraints
1 <= n <= 20001 <= primes.length <= 102 <= primes[i] <= 1000All values in primes are distinct primes.The answer fits in a 32-bit signed integer.
Hints for Super Ugly Number
Hint 1
Every super ugly number after the first is some earlier one multiplied by a prime from the list.
Hint 2
Keep one pointer per prime into the sequence built so far; the next value is the smallest of
primes[j] * ugly[idx[j]].Hint 3
Advance every pointer that produced the minimum, or duplicates creep in.
How to solve Super Ugly Number
Build the sequence in order. Each prime maintains a pointer to the earliest sequence element it has not yet multiplied; the next term is the smallest of those products.
Approach
- Start the sequence at
[1]with every pointer at index 0. - Compute
primes[j] * ugly[idx[j]]for eachjand take the minimum as the next term. - Advance every pointer whose product equals that minimum — this deduplicates values reachable in more than one way.
- Append the term and repeat until the sequence has
nentries.
Why it works
Every super ugly number greater than 1 factors as prime × (smaller super ugly number), so the candidate set above covers all of them. Because the sequence is built in increasing order and each pointer only moves forward, each candidate is offered exactly once, and advancing all tied pointers prevents the same value from being emitted twice.
Complexity
- Time —
O(n · k) forkprimes - Space —
O(n + k)
Pitfalls
- Advancing only the first tied pointer emits duplicates —
2 * 3and3 * 2would both appear. - A heap gives
O(n k log k)and is the usual alternative; the pointer version is simpler and faster here. - Intermediate products can exceed the answer, so guard the multiplication or use 64-bit arithmetic.
Reference solution
Python
from typing import List
def nthSuperUglyNumber(n: int, primes: List[int]) -> int:
ugly = [1]
idx = [0] * len(primes)
while len(ugly) < n:
nxt = min(primes[j] * ugly[idx[j]] for j in range(len(primes)))
for j in range(len(primes)):
if primes[j] * ugly[idx[j]] == nxt:
idx[j] += 1
ugly.append(nxt)
return ugly[n - 1]Java
public static int nthSuperUglyNumber(int n, int[] primes) {
long[] ugly = new long[n];
ugly[0] = 1;
int[] idx = new int[primes.length];
for (int i = 1; i < n; i++) {
long next = Long.MAX_VALUE;
for (int j = 0; j < primes.length; j++) {
long cand = (long) primes[j] * ugly[idx[j]];
if (cand < next) next = cand;
}
for (int j = 0; j < primes.length; j++) {
if ((long) primes[j] * ugly[idx[j]] == next) idx[j]++;
}
ugly[i] = next;
}
return (int) ugly[n - 1];
}C++
int nthSuperUglyNumber(int n, vector<int>& primes) {
vector<long long> ugly(n);
ugly[0] = 1;
vector<int> idx(primes.size(), 0);
for (int i = 1; i < n; i++) {
long long next = LLONG_MAX;
for (size_t j = 0; j < primes.size(); j++) {
long long cand = (long long) primes[j] * ugly[idx[j]];
if (cand < next) next = cand;
}
for (size_t j = 0; j < primes.size(); j++) {
if ((long long) primes[j] * ugly[idx[j]] == next) idx[j]++;
}
ugly[i] = next;
}
return (int) ugly[n - 1];
}JavaScript
var nthSuperUglyNumber = function(n, primes) {
var ugly = [1];
var idx = [];
for (var t = 0; t < primes.length; t++) idx.push(0);
while (ugly.length < n) {
var next = Infinity;
for (var j = 0; j < primes.length; j++) {
var cand = primes[j] * ugly[idx[j]];
if (cand < next) next = cand;
}
for (var k = 0; k < primes.length; k++) {
if (primes[k] * ugly[idx[k]] === next) idx[k]++;
}
ugly.push(next);
}
return ugly[n - 1];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming · Heaps and Priority Queues