Ugly Number II
Find the nth ugly number (only prime factors 2, 3, 5) using a min-heap or DP.
Ugly Number II
Problem: An ugly number is a positive integer whose only prime factors are 2, 3, and 5. Find the nth ugly number. The sequence starts: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ...
Example:
- Input:
n = 10 - Output:
12
Note
Every ugly number is just a previous ugly number multiplied by 2, 3, or 5. Start from 1 and keep generating the next smallest ugly number.
How to Think About It
Starting point: Check every positive integer one by one — divide by 2, 3, 5 repeatedly; if what's left is 1, it's ugly. Count until you hit the nth. Works but extremely slow for large n since most integers aren't ugly.
The core insight: You're wasting time on non-ugly numbers. Every ugly number is just a previous ugly number multiplied by 2, 3, or 5. So you can generate ugly numbers directly — no need to check anything else.
The generation rule: Start with {1}. From any ugly number u, the candidates for the next ugly numbers are u×2, u×3, u×5. The smallest unvisited candidate is always the next ugly number in the sequence.
Why a min-heap? You're generating candidates from multiple sources (every previously found ugly number, multiplied by 2, 3, or 5). You always need the smallest unprocessed candidate — that's a textbook min-heap job. Pop the minimum, generate its three children, push them.
Avoiding duplicates: The same value can be generated multiple ways — 2×3 = 6 and 3×2 = 6. Use a visited set to skip values already in the heap.
The pattern: Generate-and-expand with a min-heap — a common pattern when the search space is infinite but locally structured.
Brute Force
View Brute Force
Optimal — Min-Heap
View Optimal Solution
| Approach | Time | Space |
|---|---|---|
| Check every integer | O(n × U) very slow | O(1) |
| Min-Heap | O(n log n) | O(n) |