Question

Design an algorithm to find the kth number such that the only prime factors are 3, 5, and 7.

Solution

This is very difficult question. All I can say is, just memorize this solution.

It works like this:

1. Init 3 queues, with initial value of 3, 5 and 7 respectively.
2. Fetch the smallest element x at the head of 3 queues.
3. Add number x to the result list, then:
   1. if number x comes from queue3, add 3x, 5x and 7x into 3 queues
   2. if number x comes from queue5, add 5x and 7x into queue5 and queue7
   3. if number x comes from queue7, add 7x into queue7
4. Fetch next smallest element and do this recursively.

A dp solution is available. It’s using the same method actually, but less intuitive.

Code

not written