Domain 2MediumCORE

Super Ugly Number

We are asked to find the $n$-th number in a sequence where every element is composed solely of primes from the given primes array (e.g., if primes = [2, 3], valid numbers are powers of 2 and 3).

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Math#Heap

313. Super Ugly Number

Model: qwen3.5:9b
Topics: Math,Heap
FAANG asked: 1
Acceptance rate: 46.3%


Problem Breakdown

We are asked to find the nn-th number in a sequence where every element is composed solely of primes from the given primes array (e.g., if primes = [2, 3], valid numbers are powers of 2 and 3).

Key Definitions & Constraints:

  • Input: An integer n (1≤n≤1061 \le n \le 10^6) and a sorted list of unique prime integers.
  • Output: The nn-th super ugly number (guaranteed to fit in a standard signed 32-bit int).
  • Implicit Logic:
    • 1 is always the first super ugly number because it has no prime factors, satisfying the condition vacuously. This matches Example 2 where n=1.
    • Since we need the nn-th element in a sorted sequence of generated numbers, this implies an iterative generation process rather than checking every integer up to some bound (which would be inefficient).

Intuition

If I were to brute force this by iterating through integers and factorizing them to check if their prime factors are within primes, the time complexity would explode because we’d have to skip non-ugly numbers.

A better way is to think about how super ugly numbers are constructed: they must be formed by multiplying a previously found super ugly number by one of the primes in our list. Imagine each prime pip_i generates its own stream of candidates (e.g., for prime 2, we have 1×21\times2, then later 4×24\times2, etc.). We want to merge these streams into a single sorted sequence without duplicates.

This is structurally identical to the “Ugly Number II” problem or merging K sorted lists. The challenge here is handling duplicates. For example, if we have primes [2, 7], 1414 can be reached by multiplying 2 with a previous ugly number that was divisible by 7, OR by multiplying 7 with an ugly number divisible by 2. If we simply pick the minimum candidate and advance one pointer, we might miss advancing another stream or generate duplicates. The solution is to find the global minimum among all current candidates from each prime’s stream, add it to our sequence, and then advance every pointer that produced this specific minimum value. This ensures sorted order and eliminates duplicates naturally without needing a hash set (which would be slower).

Approach

  1. Initialize an array ugly of size nn with ugly[0] = 1.
  2. Maintain an index pointer for each prime in the list, initially all pointing to ugly[0]. Let’s call this idxs.
  3. Iterate from position i=1i = 1 to n−1n-1:
    • For every prime at index jj, calculate a candidate value: primes[j] * ugly[idxs[j]].
    • Find the minimum of these candidates; let’s call it next_val.
    • Assign ugly[i] = next_val.
    • Crucial Step: For every prime jj where the candidate value equals next_val, increment its pointer (idxs[j]). This ensures we don’t reuse a number that has already been used to generate this specific ugly number, preventing duplicates.
  4. Return ugly[n-1].

Complexity Analysis

  • Time: O(n⋅k)O(n \cdot k), where nn is the target index and kk is the length of primes (up to 100). In each iteration we scan all primes (kk) to find the minimum. With n=106n=10^6, this results in roughly 10810^8 operations, which fits within typical time limits for C++/Java and is acceptable logic-wise for Python given the constraints on primes.
  • Space: O(n)O(n) to store the sequence of ugly numbers. We also use O(k)O(k) space for the pointers array, but this is negligible compared to the result array.

Solution

import math

def nthSuperUglyNumber(n: int, primes: list[int]) -> int:
    # Initialize the super ugly number sequence with 1 as the first element
    ugly = [0] * n
    ugly[0] = 1
    
    # Pointers for each prime to track which ugly number we multiply next
    idxs = [0] * len(primes)
    
    # Iterate from index 1 up to n-1 to fill the rest of the sequence
    for i in range(1, n):
        min_val = float('inf')
        
        # Calculate candidate values for each prime stream and find the minimum
        for j in range(len(primes)):
            val = primes[j] * ugly[idxs[j]]
            if val < min_val:
                min_val = val
        
        # Store the next super ugly number
        ugly[i] = min_val
        
        # Advance pointers for all primes that produced this minimum value.
        # This step is critical to avoid duplicates (e.g., 2*7 vs 7*2).
        for j in range(len(primes)):
            if primes[j] * ugly[idxs[j]] == min_val:
                idxs[j] += 1
                
    return ugly[n - 1]

Edge Cases Handled

  • n = 1: The loop range(1, n) does not execute. We immediately return ugly[0], which is initialized to 1. This correctly handles the base case where only the number 1 exists in the sequence.
  • Single Prime: If primes has length 1 (e.g., [2]), the inner loop runs once per iteration, effectively generating powers of that prime (20=1,21=2,…2^0=1, 2^1=2, \dots). The pointer logic still holds correctly as there is only one candidate to compare.
  • Large n: Since Python handles large integers automatically and we store the sequence in a list, overflow isn’t an issue for storage (though constraints guarantee result fits in 32-bit int). We rely on O(n)O(n) space which scales with input size as required.