Numbers Made of Twos, Threes and Fives

Medium

List, in increasing order, every positive integer whose only prime factors are 2, 3 and 5: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, …. The number 1 is included. Given k, return the k-th number in this list (counting from 1).

Example 1

k=7 → 8

The sequence starts 1, 2, 3, 4, 5, 6, 8. The seventh number is 8 (7 is skipped because 7 is a prime factor).

Example 2

k=12 → 16

Next come 9, 10, 12, 15, 16, so the twelfth is 16. 11, 13 and 14 are skipped.

Example 3

k=1 → 1

1 has no prime factors at all, so it opens the list.

Constraints

1 ≤ k ≤ 1690

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Hash Table Math Dynamic Programming Heap (Priority Queue)

Similar problems

Fewest Lines Through the Dots Medium Messages Behind Key Presses Medium Picks Without a Fixed Gap Medium The Growing String Medium A Level Stretch of Fence Medium

Input

k=7

Expected

Run checks the first 3 tests in your browser. Submit checks all 41 tests on the server, hidden ones included.