[CC150v4] 10.7 Ugly Numbers (Hamming numbers)

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