Design an algorithm to find kth number such that the only prime factors are 3, 5, 7. note that
Answers
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.
Hope this helps!