Find the kth number with only prime factors of 3, 5 and 7 | Hello World
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.
Read full article from Find the kth number with only prime factors of 3, 5 and 7 | Hello World
No comments:
Post a Comment