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 -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() and a sorted list of unique prime integers. - Output: The -th super ugly number (guaranteed to fit in a standard signed 32-bit int).
- Implicit Logic:
1is always the first super ugly number because it has no prime factors, satisfying the condition vacuously. This matches Example 2 wheren=1.- Since we need the -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 generates its own stream of candidates (e.g., for prime 2, we have , then later , 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], 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
- Initialize an array
uglyof size withugly[0] = 1. - Maintain an index pointer for each prime in the list, initially all pointing to
ugly[0]. Let’s call thisidxs. - Iterate from position to :
- For every prime at index , 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 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.
- For every prime at index , calculate a candidate value:
- Return
ugly[n-1].
Complexity Analysis
- Time: , where is the target index and is the length of
primes(up to 100). In each iteration we scan all primes () to find the minimum. With , this results in roughly operations, which fits within typical time limits for C++/Java and is acceptable logic-wise for Python given the constraints onprimes. - Space: to store the sequence of ugly numbers. We also use 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 looprange(1, n)does not execute. We immediately returnugly[0], which is initialized to1. This correctly handles the base case where only the number 1 exists in the sequence.- Single Prime: If
primeshas length 1 (e.g.,[2]), the inner loop runs once per iteration, effectively generating powers of that prime (). 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 space which scales with input size as required.