Super Ugly Number

Medium
710.

Super Ugly Number

Super Ugly Number is a medium coding problem on dynamic programming, math and heap, asked in Amazon, Google and Microsoft interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[]} primes
 * @return {number}
 */
var nthSuperUglyNumber = function(n, primes) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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.

Hints for Super Ugly Number

  1. Hint 1

    Every super ugly number after the first is some earlier one multiplied by a prime from the list.

  2. 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]].

  3. 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

  1. Start the sequence at [1] with every pointer at index 0.
  2. Compute primes[j] * ugly[idx[j]] for each j and take the minimum as the next term.
  3. Advance every pointer whose product equals that minimum — this deduplicates values reachable in more than one way.
  4. 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]

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