Ugly Number II
Medium · Heap & Counting · Hash Table · Math · Dynamic Programming · Heap (Priority Queue)
Problem
An ugly number is a positive integer whose only prime factors are 2, 3 and 5. By convention 1 is the first ugly number.
Given n, return the n-th ugly number in increasing order.
Examples
Input: n = 7 Output: 8
The sequence starts 1, 2, 3, 4, 5, 6, 8: 7 is prime, so it is not ugly.
Input: n = 15 Output: 24
Continuing: 9, 10, 12, 15, 16, 18, 20, 24.
Input: n = 1 Output: 1
1 is the first ugly number by convention.
Constraints
- 1 <= n <= 1690
Approaches
- Min-heap with a seen set — time O(n log n), space O(n)
Follow-up
What if the primes were an arbitrary list of k primes instead of 2, 3 and 5? The same idea uses k pointers and takes O(n · k) time, or a heap of the k candidates for O(n log k).
Related problems
Start free on Cariara · Coding problems · System design studio
