Design an algorithm to find the kth number such that the only prime factors are 3, 5, and 7.
This is very difficult question. All I can say is, just memorize this solution.
It works like this:
- Init 3 queues, with initial value of 3, 5 and 7 respectively.
- Fetch the smallest element x at the head of 3 queues.
- Add number x to the result list, then:
- if number x comes from queue3, add 3x, 5x and 7x into 3 queues
- if number x comes from queue5, add 5x and 7x into queue5 and queue7
- if number x comes from queue7, add 7x into queue7
- Fetch next smallest element and do this recursively.
A dp solution is available. It’s using the same method actually, but less intuitive.