Domain 2MediumCORE

Ugly Number II

We need to find the $n$-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 ($1 le n le 1690$). Output: The $n$-th ugly number. Implicit Constraints: Since we need the nth* in order, duplicates must be avoided (e.g., $2times3 = 6$ and $3times2=6$ 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.

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

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 nn-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 (1≤n≤16901 \le n \le 1690).
  • Output: The nn-th ugly number.
  • Implicit Constraints: Since we need the nth in order, duplicates must be avoided (e.g., 2×3=62\times3 = 6 and 3×2=63\times2=6 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 N=1690N=1690, the answer is large enough that checking every integer up to it would be inefficient (O(N⋅M)O(N \cdot M) where MM 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 min⁡(current_ugly×2,current_ugly×3,current_ugly×5)\min(\text{current\_ugly} \times 2, \text{current\_ugly} \times 3, \text{current\_ugly} \times 5). 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 (i+1)(i+1)-th ugly number.

  1. Initialize dp[0] = 1. This is our starting point.
  2. Maintain three pointers: p2, p3, and p5, all initialized to index 0. These represent indices in dp that, when multiplied by their respective factors (2, 3, 5), produce candidates for the next ugly number.
  3. Iterate from i=1i = 1 to n−1n-1:
    • Calculate potential next values: next_ugly_2, next_ugly_3, and next_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 2×6=122 \times 6 = 12 and 3×4=123 \times 4 = 12, both corresponding indices must advance).
  4. Return dp[n-1].

Complexity Analysis

  • Time: O(n)O(n). We perform a constant number of operations (comparisons, multiplications, pointer increments) for each step from 0 to nn.
  • Space: O(n)O(n) to store the sequence in our dp array. 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. Returns dp[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 2×p32 \times p_3 and 3×p23 \times p_2 yield the same minimum, if val == min_val checks 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 (n≤1690n \le 1690).