Ugly Number II

Find the nth ugly number using dynamic programming and three pointers.

dynamic programming math pointers

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5. By convention, 1 is the first ugly number.

Write a function `nth_ugly_number(n: int) -> int` that returns the nth ugly number (1-indexed).

You must implement an efficient solution — the naive approach of generating and checking every integer will be too slow for large n. Use dynamic programming with three pointers to generate ugly numbers in ascending order.

Constraints

1 ≤ n ≤ 1690
The answer fits within a signed 32-bit integer.
Expected time complexity: O(n) with O(n) space.

Example

>>> nth_ugly_number(1)
1
>>> nth_ugly_number(10)
12
>>> nth_ugly_number(11)
15
>>> nth_ugly_number(1690)
2123366400

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of generating ugly numbers by multiplying earlier ugly numbers by 2, 3, and 5.

Maintain three indices (pointers) for multiples of 2, 3, and 5.

At each step, pick the smallest product among the three and advance the corresponding pointer(s).

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.