Ugly Numbers (Heap-based)

Find the nth ugly number using heap-based approach

Language Selection

Choose your preferred programming language

Showing: Python

Ugly Numbers (Heap-based)

Problem Statement

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.

Given an integer n, return the nth ugly number.

Input/Output Specifications

Input:
- n: Integer (1 <= n <= 1690)
Output: Integer representing the nth ugly number

Constraints

1 <= n <= 1690

Examples

Example 1:

Input: n = 10
Output: 12
Explanation: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] are the first 10 ugly numbers.
Note: 1 is considered an ugly number.

Example 2:

Input: n = 1
Output: 1
Explanation: 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.

Solution Approaches

Approach 1: Min-Heap (Optimal)

Algorithm Explanation:

Use min-heap to generate ugly numbers in sorted order
Start with 1 in heap
For each iteration:
- Extract minimum from heap
- Generate new ugly numbers by multiplying with 2, 3, 5
- Use set to avoid duplicates
- Add new numbers to heap
Return nth extracted number

Implementation:

Python:

import heapq

def nth_ugly_number_heap(n):
    """
    Find nth ugly number using min-heap
    Time: O(n log n)
    Space: O(n)
    """
    if n <= 0:
        return 0
    
    min_heap = [1]
    seen = {1}
    factors = [2, 3, 5]
    
    for _ in range(n):
        ugly = heapq.heappop(min_heap)
        
        # Generate new ugly numbers
        for factor in factors:
            new_ugly = ugly * factor
            if new_ugly not in seen:
                seen.add(new_ugly)
                heapq.heappush(min_heap, new_ugly)
    
    return ugly

# Alternative implementation with better space efficiency
def nth_ugly_number_heap_v2(n):
    """
    Optimized heap approach with set cleanup
    Time: O(n log n)
    Space: O(n)
    """
    heap = [1]
    seen = {1}
    
    for i in range(n):
        num = heapq.heappop(heap)
        
        if i == n - 1:
            return num
        
        for factor in [2, 3, 5]:
            new_num = num * factor
            if new_num not in seen:
                seen.add(new_num)
                heapq.heappush(heap, new_num)
    
    return -1  # Should never reach here

Java:

import java.util.*;

class Solution {
    /**
     * Find nth ugly number using min-heap
     * Time: O(n log n)
     * Space: O(n)
     */
    public int nthUglyNumber(int n) {
        if (n <= 0) return 0;
        
        PriorityQueue<Long> minHeap = new PriorityQueue<>();
        Set<Long> seen = new HashSet<>();
        int[] factors = {2, 3, 5};
        
        minHeap.offer(1L);
        seen.add(1L);
        
        long ugly = 1;
        
        for (int i = 0; i < n; i++) {
            ugly = minHeap.poll();
            
            for (int factor : factors) {
                long newUgly = ugly * factor;
                if (!seen.contains(newUgly)) {
                    seen.add(newUgly);
                    minHeap.offer(newUgly);
                }
            }
        }
        
        return (int) ugly;
    }
}

Go:

import (
    "container/heap"
)

type MinHeap []int64

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) {
    *h = append(*h, x.(int64))
}

func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

// nthUglyNumber - Find nth ugly number using min-heap
// Time: O(n log n), Space: O(n)
func nthUglyNumber(n int) int {
    if n <= 0 {
        return 0
    }
    
    minHeap := &MinHeap{1}
    heap.Init(minHeap)
    seen := make(map[int64]bool)
    seen[1] = true
    factors := []int64{2, 3, 5}
    
    var ugly int64
    
    for i := 0; i < n; i++ {
        ugly = heap.Pop(minHeap).(int64)
        
        for _, factor := range factors {
            newUgly := ugly * factor
            if !seen[newUgly] {
                seen[newUgly] = true
                heap.Push(minHeap, newUgly)
            }
        }
    }
    
    return int(ugly)
}

JavaScript:

class MinHeap {
    constructor() {
        this.heap = [];
    }
    
    push(val) {
        this.heap.push(val);
        this.bubbleUp();
    }
    
    pop() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop();
        
        const min = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.bubbleDown();
        return min;
    }
    
    size() {
        return this.heap.length;
    }
    
    bubbleUp() {
        let idx = this.heap.length - 1;
        while (idx > 0) {
            const parentIdx = Math.floor((idx - 1) / 2);
            if (this.heap[parentIdx] <= this.heap[idx]) break;
            [this.heap[parentIdx], this.heap[idx]] = [this.heap[idx], this.heap[parentIdx]];
            idx = parentIdx;
        }
    }
    
    bubbleDown() {
        let idx = 0;
        while (2 * idx + 1 < this.heap.length) {
            let minChildIdx = 2 * idx + 1;
            if (2 * idx + 2 < this.heap.length && 
                this.heap[2 * idx + 2] < this.heap[minChildIdx]) {
                minChildIdx = 2 * idx + 2;
            }
            
            if (this.heap[idx] <= this.heap[minChildIdx]) break;
            [this.heap[idx], this.heap[minChildIdx]] = [this.heap[minChildIdx], this.heap[idx]];
            idx = minChildIdx;
        }
    }
}

/**
 * Find nth ugly number using min-heap
 * Time: O(n log n)
 * Space: O(n)
 */
function nthUglyNumber(n) {
    if (n <= 0) return 0;
    
    const minHeap = new MinHeap();
    const seen = new Set();
    const factors = [2, 3, 5];
    
    minHeap.push(1);
    seen.add(1);
    
    let ugly = 1;
    
    for (let i = 0; i < n; i++) {
        ugly = minHeap.pop();
        
        for (const factor of factors) {
            const newUgly = ugly * factor;
            if (!seen.has(newUgly)) {
                seen.add(newUgly);
                minHeap.push(newUgly);
            }
        }
    }
    
    return ugly;
}

Approach 2: Dynamic Programming (More Efficient)

Algorithm Explanation:

Use three pointers for multiples of 2, 3, and 5
Generate ugly numbers in sequence
Always take minimum of next possible ugly numbers
Advance corresponding pointers

Implementation:

Python:

def nth_ugly_number_dp(n):
    """
    Find nth ugly number using dynamic programming
    Time: O(n)
    Space: O(n)
    """
    if n <= 0:
        return 0
    
    ugly = [0] * n
    ugly[0] = 1
    
    # Pointers for multiples of 2, 3, 5
    i2 = i3 = i5 = 0
    
    # Next multiples
    next_2 = 2
    next_3 = 3
    next_5 = 5
    
    for i in range(1, n):
        # Choose minimum of next possible ugly numbers
        ugly[i] = min(next_2, next_3, next_5)
        
        # Update pointers and next multiples
        if ugly[i] == next_2:
            i2 += 1
            next_2 = ugly[i2] * 2
        
        if ugly[i] == next_3:
            i3 += 1
            next_3 = ugly[i3] * 3
        
        if ugly[i] == next_5:
            i5 += 1
            next_5 = ugly[i5] * 5
    
    return ugly[n - 1]

Key Insights

Heap Generation: Generate ugly numbers in sorted order using min-heap
Duplicate Prevention: Use set to avoid processing same number multiple times
Factor Multiplication: Each ugly number generates 3 new candidates
DP Optimization: Three-pointer approach is more space and time efficient

Edge Cases

n = 1: First ugly number is 1
Small n: Handle n <= 6 (basic ugly numbers)
Large Numbers: Prevent integer overflow
Invalid Input: Handle n <= 0

Test Cases

def test_nth_ugly_number():
    # Basic cases
    assert nth_ugly_number_heap(1) == 1
    assert nth_ugly_number_heap(10) == 12
    
    # First few ugly numbers: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12]
    expected = [1, 2, 3, 4, 5, 6, 8, 9, 10, 12]
    for i in range(1, 11):
        assert nth_ugly_number_heap(i) == expected[i-1]
    
    # Test DP approach
    assert nth_ugly_number_dp(10) == 12
    assert nth_ugly_number_dp(1) == 1
    
    # Larger test case
    assert nth_ugly_number_heap(15) == 24
    assert nth_ugly_number_dp(15) == 24
    
    print("All tests passed!")

test_nth_ugly_number()

Interview Tips

Define Ugly Numbers: Explain that only prime factors are 2, 3, 5
Heap Approach: Show how to generate in sorted order
Duplicate Handling: Explain necessity of set for avoiding duplicates
DP Optimization: Mention more efficient three-pointer approach
Space-Time Tradeoff: Compare heap vs DP approaches

Follow-up Questions

Ugly Numbers II: Find all ugly numbers up to n
Super Ugly Numbers: Generalize to any set of prime factors
Kth Ugly Number: Find kth ugly number efficiently
Range Query: Count ugly numbers in a given range
Streaming: Generate ugly numbers in real-time

Common Mistakes

Missing Duplicates: Not handling duplicate generation correctly
Integer Overflow: Not using appropriate data types for large numbers
Wrong Initialization: Starting with wrong base case
Heap Management: Incorrectly managing heap operations
Edge Cases: Not handling n=1 or invalid inputs

Concept Explanations

Ugly Number Generation: The key insight is that every ugly number (except 1) is formed by multiplying a smaller ugly number by 2, 3, or 5. This creates a natural tree structure that we can traverse using a heap.

Heap vs DP Trade-off: While the heap approach is more intuitive and generalizable, the DP approach with three pointers is more efficient for this specific problem because it avoids the overhead of heap operations and duplicate detection.

When to Apply: Use heap approach when you need to generate numbers in a specific order with multiple generation rules, or when the problem can be generalized to different factors. The pattern is useful for sequence generation problems where each element depends on previous elements through multiple transformation rules.