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

It is a difficult question. But lets try to examplify it first.

we will have 3, 5, 7, 9, 15, 21, 25, 27, 35 , 45 … The way we do it is we first get 3, 5 and 7, then we multiply 3 with 3, 5, 7 and then 5 with 3, 5, 7 and 7 with 3,5,7, we do not know the order of the result, but what we do know is that 3^(i+1)*5^j*7^k > 3^i*5^j*7^k, same for 7 and 9, so we can have 3 queues Q3, Q5 and Q7, to store the elements of factor 3, 5 and 7, and a result to count the number of elements.

Process goes as follows

1. add 3, 5 and 7 to the corresponding queue.

2. remove the smallest element out of the head of the three Queue and count++.

3. if element x was removed from Q3, add 3*x, 5*x and 7*x to Q3, Q5 and Q7

if element x was removed from Q5, add 5*x and 7*x to Q5 and Q7

if element x was removed from Q7, add 7*x to Q7

(This step will make sure that when you removed a number that is 3^i*5^j*7^k, the i+1, j+1 and k+1 number will be pushed into the corresponding queue)

4. if has not count to k, go back to 2.

### Like this:

Like Loading...

*Related*