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.
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) |