264. Ugly Number II
Model: qwen3.5:9b
Topics: Math,Dynamic Programming,Heap
FAANG asked: 1
Acceptance rate: 43.0%
Problem Breakdown
We need to find the -th number in an ordered sequence where every element has prime factors only 2, 3, and/or 5 (1 is included as it has no other prime factors).
- Input: Integer
n(). - Output: The -th ugly number.
- Implicit Constraints: Since we need the nth in order, duplicates must be avoided (e.g., and should not appear twice in our sequence). We also assume standard integer limits apply for languages like Java/C++, though Python handles large integers automatically.
Intuition
A brute-force approach would iterate through every positive integer starting from 1, check if it is ugly (by dividing out factors of 2, 3, and 5 until none remain), and count valid ones until we reach n.
- Why this fails: The density of ugly numbers decreases as values grow. Checking non-ugly numbers wastes time. For , the answer is large enough that checking every integer up to it would be inefficient ( where is value magnitude).
- Key Insight: Ugly numbers are generated by multiplying existing ugly numbers by 2, 3, or 5. Since we want them in sorted order, the next ugly number must be . We can maintain pointers to track which existing ugly numbers are candidates for multiplication by each factor.
Approach
We use a Dynamic Programming array dp where dp[i] stores the -th ugly number.
- Initialize
dp[0] = 1. This is our starting point. - Maintain three pointers:
p2,p3, andp5, all initialized to index 0. These represent indices indpthat, when multiplied by their respective factors (2, 3, 5), produce candidates for the next ugly number. - Iterate from to :
- Calculate potential next values:
next_ugly_2,next_ugly_3, andnext_ugly_5. - The actual next ugly number is the minimum of these three candidates.
- Update pointers for any factor that produced this minimum value to ensure we don’t reuse it or generate duplicates (e.g., if and , both corresponding indices must advance).
- Calculate potential next values:
- Return
dp[n-1].
Complexity Analysis
- Time: . We perform a constant number of operations (comparisons, multiplications, pointer increments) for each step from 0 to .
- Space: to store the sequence in our
dparray. This is necessary because we need random access to previous ugly numbers via pointers.
Solution
def nthUglyNumber(n: int) -> int:
# dp[i] will hold the (i+1)-th ugly number
dp = [0] * n
# Base case: 1 is always an ugly number and starts our sequence
dp[0] = 1
# Pointers for factors 2, 3, and 5.
# They track the index in 'dp' that we should multiply next by each factor.
p2, p3, p5 = 0, 0, 0
for i in range(1, n):
# Calculate candidates from current pointers multiplied by their factors
val_2 = dp[p2] * 2
val_3 = dp[p3] * 3
val_5 = dp[p5] * 5
# The next ugly number is the minimum of these candidates to maintain sorted order
min_val = min(val_2, val_3, val_5)
# Assign it to current position in DP array
dp[i] = min_val
# Increment pointers for any factor that produced this value.
# We must increment all matching factors to avoid duplicates (e.g., 6 is both 2*3 and 3*2).
if val_2 == min_val:
p2 += 1
if val_3 == min_val:
p3 += 1
if val_5 == min_val:
p5 += 1
return dp[n - 1]
Edge Cases Handled
- n = 1: The loop
range(1, n)does not execute. Returnsdp[0]which is initialized to 1. Correctly handles the first ugly number case without entering logic loops unnecessarily. - Duplicate Generation (e.g., value 6): If both and yield the same minimum,
if val == min_valchecks are independent for each pointer. Both corresponding pointers increment in that iteration, ensuring we skip over duplicates immediately rather than storing them twice. - Overflow: While not an issue in Python (arbitrary precision integers), this logic ensures values grow strictly monotonically within the constraints provided ().