All problems

Ugly Number II

Medium · heap

Call a positive whole number *tidy* if the only prime numbers that divide it are 2, 3 and 5. The number 1 is tidy, because no prime divides it. A number such as 14 is not tidy, because 7 divides it.

Written in increasing order, the tidy numbers begin 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, and so on. Notice that 7, 11 and 14 are missing.

Given n, return the nth tidy number, counting from 1.

Examples

Example 1

Input: n = 10

Output: 12

The first ten tidy numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12.

Example 2

Input: n = 1

Output: 1

1 is the first tidy number.

Example 3

Input: n = 15

Output: 24

The list continues 15, 16, 18, 20, 24 after the tenth number, so the fifteenth is 24.

Constraints