DSA problem
Ugly Number II
An ugly number is a positive integer whose only prime factors are limited to 2, 3, and 5. Given an integer n, return the n-th ugly number in the sorted sequence. The sequence begins 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, .... Notably, 1 is included by convention and 7, 11, 13, 14 are excluded because each contains a prime factor outside {2, 3, 5}.
A brute-force approach that tests every integer with the Ugly Number predicate until we have counted n uglies is correct but extremely slow because ugly numbers thin out quickly — there are only roughly n / log^3 n uglies up to n, so we waste enormous effort on non-uglies.
A clean min-heap solution maintains a priority queue seeded with {1} and a "seen" set. Repeatedly pop the smallest value x; push 2x, 3x, and 5x if they have not been seen before. After n pops, the value popped most recently is the answer. This is O(n log n) time and O(n) space, taking advantage of the heap to always emit ugly numbers in order without duplicates.
The optimal DP solution avoids the heap entirely. Maintain three indices i2, i3, i5 into the growing array of ugly numbers, each indicating the next position whose value should be multiplied by 2, 3, and 5 respectively. At each step the next ugly is the minimum of uglies[i2]*2, uglies[i3]*3, uglies[i5]*5. Whichever generators produced that minimum are advanced (more than one if multiple are tied), which prevents duplicates. This runs in O(n) time and O(n) space.
Examples
n = 1012n = 11n = 78Constraints
- 1 <= n <= 1690
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.