Number Theory · 163Medium
Ugly Number II
An ugly number has no prime factors other than 2, 3 and 5. Given an integer n, return the nth ugly number (1-indexed). By convention 1 is ugly.
Constraints
- 1 <= n <= 1690
Examples
nthUglyNumber(10) -> 12 // 1,2,3,4,5,6,8,9,10,12 nthUglyNumber(1) -> 1 // 1 is the first ugly number nthUglyNumber(7) -> 8 nthUglyNumber(2) -> 2 nthUglyNumber(11) -> 15 // 14 is skipped — it has the factor 7 nthUglyNumber(1690) -> 2123366400 // the largest n allowed
Edge cases
- 1 counts as the first ugly number.
- Duplicates must be skipped: 6 arises as both 2*3 and 3*2.
Show the target complexity (spoiler)
- Naive
- O(n * k) time — check each integer in turn by dividing out 2s, 3s and 5s.
- Target
- O(n) time, O(n) space — three pointers into the growing sequence, taking the minimum of (2*a, 3*b, 5*c) each step and advancing EVERY pointer that produced it.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/22-number-theory/163-ugly-number-ii.js ./practice c 163