Kth number with only prime factors of 3, 5 and 7.

Fact:

• Kth Multiple of 3, 5 and 7 = 3k * 5k * 7k

Solution:

• Take 3 queues
  • Queue-3 to hold 3 multiples
  • Queue-5 to hold 5 multiples
  • Queue-7 to hold 7 multiples
• Remove minimum value from all three queues
• If we removed from Q3 then
• add Q3 * – If we removed from Q5 then
• add Q5 * – If we removed from Q7 then
• add Q7 * – – We’ll not add to Q3 and Q5 because it will be duplicate

Algorithm:

1. Take three queue namely Q3, Q5 and Q7
2. Add 1 to Q3
3. Iterate 1 to K
   1. Fetch minimum_value from all three Queues
   2. If minimum_value == Q3.peek() then
      1. Q3.removeMin()
      2. Add Q3
   3.  If minimum_value == Q5.peek() then
      1. Q5.removeMin()
      2. Add Q5
   4. If minimum_value == Q7.peek() then
      1. Q7.removeMin()
   5. Add Q7 * – return minimum_value

Latest Source Code:
Github: KthMultipleNumberOfThreeFiveAndSeven.java

Output:

When k==1 then Multiple = 1
When k==2 then Multiple = 3
When k==3 then Multiple = 5
When k==4 then Multiple = 7
When k==5 then Multiple = 9
When k==6 then Multiple = 15
When k==7 then Multiple = 21
When k==8 then Multiple = 25