Problem Description

An ugly number is defined as a positive integer that only has prime factors of 2, 3, and 5. In other words, when you break down an ugly number into its prime factors, you'll only find combinations of these three primes.

For example:

• 1 is considered an ugly number (by convention, as it has no prime factors)
• 2, 3, 4, 5, 6, 8, 9, 10, 12 are all ugly numbers
• 2 = 2
• 6 = 2 × 3
• 12 = 2² × 3
• 7, 11, 14 are NOT ugly numbers because:
  • 7 has prime factor 7
  • 11 has prime factor 11
  • 14 = 2 × 7 (contains prime factor 7)

The problem asks you to find the nth ugly number in the sequence when ugly numbers are arranged in ascending order.

The sequence of ugly numbers starts as: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...

Given an integer n, you need to return the nth number in this sequence. For instance:

• If n = 1, return 1
• If n = 10, return 12
• If n = 11, return 15

Intuition

The key observation is that every ugly number (except 1) is formed by multiplying a smaller ugly number by 2, 3, or 5. This means if we have an ugly number x, then 2x, 3x, and 5x are also ugly numbers.

Starting with the smallest ugly number 1, we can generate new ugly numbers by multiplying it by 2, 3, and 5, giving us 2, 3, and 5. Then from 2, we can generate 4, 6, and 10. From 3, we get 6, 9, and 15, and so on.

The challenge is maintaining the order - we need to generate ugly numbers in ascending order to find the nth one. If we simply generate all possible ugly numbers recursively, we'd create duplicates (like 6 from both 2×3 and 3×2) and lose track of the ordering.

The solution uses a min-heap (priority queue) to always extract the smallest unprocessed ugly number. Here's the thought process:

1. Start with 1 in the heap
2. Extract the smallest number from the heap - this is our next ugly number in sequence
3. Generate three new candidates by multiplying this number by 2, 3, and 5
4. Add these new candidates to the heap (if not already seen)
5. Repeat until we've found n ugly numbers

The heap automatically maintains the sorted order for us - we always get the next smallest ugly number when we pop from it. The visited set prevents us from adding duplicates (like when both 2×3 and 3×2 produce 6).

This approach elegantly handles the generation and ordering problem simultaneously - we generate ugly numbers on-the-fly in sorted order, rather than generating many numbers and then sorting them.

Solution Approach

The implementation uses a min-heap combined with a hash set to efficiently generate ugly numbers in ascending order.

Data Structures Used:

• h: A min-heap (priority queue) that stores candidate ugly numbers, always keeping the smallest at the top
• vis: A hash set that tracks which ugly numbers we've already seen to avoid duplicates
• ans: Variable to store the current ugly number being processed

Algorithm Steps:

1. Initialize the heap with [1] and the visited set with {1}. Set ans = 1 as our starting point.

2. Main Loop - Repeat n times:

   • Extract minimum: Pop the smallest number from the heap using heappop(h) and store it in ans
   • Generate new candidates: For each prime factor in [2, 3, 5]:
     • Calculate nxt = ans * v where v is the current prime factor
     • If nxt hasn't been seen before (not in vis):
       • Add nxt to the visited set
       • Push nxt onto the heap

3. Return ans after n iterations - this will be the nth ugly number

Why This Works:

The algorithm maintains the invariant that the heap always contains unprocessed ugly numbers in sorted order. Each iteration:

• Removes the smallest unprocessed ugly number (guaranteed to be the next in sequence)
• Generates exactly three potential new ugly numbers from it
• The heap automatically maintains sorted order for future iterations

Example Walkthrough for n = 10:

Iteration 1: Pop 1, generate 2, 3, 5 → heap: [2, 3, 5]
Iteration 2: Pop 2, generate 4, 6, 10 → heap: [3, 4, 5, 6, 10]
Iteration 3: Pop 3, generate 6(skip), 9, 15 → heap: [4, 5, 6, 9, 10, 15]
...
Iteration 10: Pop 12 → Return 12

The time complexity is O(n log n) due to heap operations, and space complexity is O(n) for storing the generated ugly numbers in the heap and visited set.

Example Walkthrough

Let's find the 7th ugly number using the heap-based approach.

Initial Setup:

• Heap: [1]
• Visited: {1}
• Answer: 1

Iteration 1 (n=1):

• Pop 1 from heap → ans = 1
• Generate: 1×2=2, 1×3=3, 1×5=5
• Add all to heap (none visited yet)
• Heap: [2, 3, 5], Visited: {1, 2, 3, 5}

Iteration 2 (n=2):

• Pop 2 from heap → ans = 2
• Generate: 2×2=4, 2×3=6, 2×5=10
• Add all to heap
• Heap: [3, 4, 5, 6, 10], Visited: {1, 2, 3, 4, 5, 6, 10}

Iteration 3 (n=3):

• Pop 3 from heap → ans = 3
• Generate: 3×2=6 (skip, already visited), 3×3=9, 3×5=15
• Add 9 and 15 to heap
• Heap: [4, 5, 6, 9, 10, 15], Visited: {1, 2, 3, 4, 5, 6, 9, 10, 15}

Iteration 4 (n=4):

• Pop 4 from heap → ans = 4
• Generate: 4×2=8, 4×3=12, 4×5=20
• Add all to heap
• Heap: [5, 6, 8, 9, 10, 12, 15, 20], Visited: {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 20}

Iteration 5 (n=5):

• Pop 5 from heap → ans = 5
• Generate: 5×2=10 (skip), 5×3=15 (skip), 5×5=25
• Add 25 to heap
• Heap: [6, 8, 9, 10, 12, 15, 20, 25]

Iteration 6 (n=6):

• Pop 6 from heap → ans = 6
• Generate: 6×2=12 (skip), 6×3=18, 6×5=30
• Add 18 and 30 to heap
• Heap: [8, 9, 10, 12, 15, 18, 20, 25, 30]

Iteration 7 (n=7):

• Pop 8 from heap → ans = 8
• We've completed 7 iterations, so return 8

Result: The 7th ugly number is 8.

The sequence so far: 1, 2, 3, 4, 5, 6, 8, ...

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log n)

The algorithm uses a min-heap to generate ugly numbers in ascending order. For each of the n iterations:

• We perform one heappop() operation: O(log k) where k is the current heap size
• We perform up to 3 heappush() operations (for multipliers 2, 3, and 5): 3 * O(log k)
• The set membership check nxt not in vis is O(1) on average
• The set insertion vis.add(nxt) is O(1) on average

The heap size grows as we generate numbers, but in the worst case, the heap contains at most O(n) elements (since we only pop n elements total and push at most 3n elements). Therefore, each iteration has O(log n) complexity, and with n iterations, the total time complexity is O(n log n).

Space Complexity: O(n)

The space is used by:

• The min-heap h: In the worst case, it can contain O(n) ugly numbers waiting to be processed
• The visited set vis: It stores all unique ugly numbers generated, which is bounded by O(n) since we generate at most 3n numbers (3 multipliers for each of n iterations)

Both data structures can grow to O(n) size, so the overall space complexity is O(n).

Common Pitfalls

1. Integer Overflow for Large n Values

When computing the nth ugly number for large values of n (e.g., n > 1000), the ugly numbers can grow exponentially large. Multiplying these large numbers by 2, 3, or 5 might exceed integer limits in some programming languages.

Problem Example:

# For n = 1690, the ugly number is 2^31 = 2,147,483,648
# Further multiplications could cause overflow in languages with fixed integer sizes

Solution:

• In Python, this isn't an issue due to arbitrary precision integers
• In other languages like Java or C++, use long/long long data types
• Add overflow checks if necessary:

MAX_INT = 2**31 - 1
if current_ugly > MAX_INT // 5:  # Check before multiplication
    # Handle potential overflow
    pass

2. Duplicate Generation Without Proper Tracking

A critical mistake is forgetting to check for duplicates before adding to the heap, leading to redundant processing and incorrect results.

Incorrect Implementation:

# WRONG: Missing duplicate check
for prime_factor in [2, 3, 5]:
    next_ugly = current_ugly * prime_factor
    heapq.heappush(min_heap, next_ugly)  # Duplicates will be added!

Why This Fails:

• Number 6 can be generated as both 2×3 and 3×2
• Without deduplication, 6 appears multiple times in the heap
• This causes the same number to be counted multiple times, returning wrong results

Correct Solution: Always maintain a visited set and check membership before adding:

if next_ugly not in visited:
    visited.add(next_ugly)
    heapq.heappush(min_heap, next_ugly)

3. Off-by-One Error in Loop Count

Using range(n-1) or range(n+1) instead of range(n) will return the wrong ugly number.

Common Mistake:

# WRONG: Returns (n-1)th ugly number
for _ in range(n-1):
    current_ugly = heapq.heappop(min_heap)

Correct Approach: The loop should run exactly n times to get the nth number:

for _ in range(n):
    current_ugly = heapq.heappop(min_heap)

4. Memory Consumption for Very Large n

The visited set grows linearly with n and can consume significant memory for large inputs.

Issue:

• For n = 10,000, the visited set might contain 30,000+ numbers
• Each number also grows larger, consuming more memory

Optimization: Consider using the Dynamic Programming approach with three pointers for better space efficiency:

def nthUglyNumber(self, n: int) -> int:
    ugly = [0] * n
    ugly[0] = 1
    i2 = i3 = i5 = 0
  
    for i in range(1, n):
        next_2 = ugly[i2] * 2
        next_3 = ugly[i3] * 3
        next_5 = ugly[i5] * 5
      
        ugly[i] = min(next_2, next_3, next_5)
      
        if ugly[i] == next_2: i2 += 1
        if ugly[i] == next_3: i3 += 1
        if ugly[i] == next_5: i5 += 1
  
    return ugly[n-1]

This approach uses O(n) space instead of potentially O(3n) space.