Category Archives: Queue

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

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