Super Ugly Number — Medium Problem & Solution

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.

Difficulty: Medium
Topics: Math, Dynamic Programming, 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 <= 2000
1 <= primes.length <= 10
2 <= primes[i] <= 1000
All values in primes are distinct primes.
The answer fits in a 32-bit signed integer.

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 each j and 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 n entries.

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) for k primes
Space — O(n + k)

Pitfalls

Advancing only the first tied pointer emits duplicates — 2 * 3 and 3 * 2 would 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]

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 213 math problems · the whole catalogue