problem264

README

< Previous 　　　　　　　　　　　　　　　　 Next >

264. Ugly Number II (Medium)

Given an integer n, return the nth ugly number.

Ugly number is a positive number whose prime factors only include 2, 3, and/or 5.

 

Example 1:

Input: n = 10
Output: 12
Explanation: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] is the sequence of the first 10 ugly numbers.

Example 2:

Input: n = 1
Output: 1
Explanation: 1 is typically treated as an ugly number.

 

Constraints:

• 1 <= n <= 1690

Related Topics

[Heap] [Math] [Dynamic Programming]

Similar Questions

1. Merge k Sorted Lists (Hard)
2. Count Primes (Easy)
3. Ugly Number (Easy)
4. Perfect Squares (Medium)
5. Super Ugly Number (Medium)

Hints

Hint 1

The naive approach is to call isUgly for every number until you reach the n^th one. Most numbers are not ugly. Try to focus your effort on generating only the ugly ones.

Hint 2

An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.

Hint 3

The key is how to maintain the order of the ugly numbers. Try a similar approach of merging from three sorted lists: L₁, L₂, and L₃.

Hint 4

Assume you have U_k, the k^th ugly number. Then U_k+1 must be Min(L₁ * 2, L₂ * 3, L₃ * 5).