# Solving Interview Question

**Question**

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

This question seems very simple but there is one interesting solution that I am going to explain below:

**Solution**

Let’s maintain 3 queues such that:

Q3: Has previously unseen multiples of 3

Q5: Has previously unseen multiples of 5

Q7: Has previously unseen multiples of 7

To find the minimum we only need to look at the fronts of each queue:

y=min(Q3.head(),Q5.head(),Q7.head())

Once we compute y, we need to insert 3y into Q3, 5y into Q5, 7y into Q7. And we only need to insert those elements that are not already into the other lists.

Let’s see how one number can be available in another list.

y is pulled from Q7 and we want to insert it into Q3. But y=7x(because Q7 has multiples of 7).

And we pulled y(=7x), meaning that it was the smallest value at the moment. It also means that we might have already seen 3x earlier.

At the moment we saw 3x we already inserted 7*3x into the queue.

7 * 3x=7x * 3

Let’s understand more clearly.

If we pull an element from Q7, it will be like 7 * suffix, and we know we have already handled 3*suffix and 5*suffix. In handling 3 * suffix, we inserted 7 * 3 * suffix into Q7. And in handling 5 * suffix, we know we inserted 7 * 5 * suffix into Q7. The only value remaining is 7 * 7 * suffix, so we only insert 7 * 7 * suffix into Q7.

**Example**

initialize:

Q3=3

Q5=5

Q7=7remove min=3.

insert 3*3 into Q3, 5*3 into Q5 and 7*3 into Q7

Q3=3*3

Q5=5, 5*3

Q7=7, 7*3reomove min=5.

3*5 is a duplicate, insert 5*5 into Q5 and 7*5 into Q7

Q3=3*3

Q5=5*3, 5*5

Q7=7, 7*3, 7*5remove min=7.

3*7 and 5*7 are duplicates, insert 7*7 into Q7

Q3=3*3

Q5=5*3, 5*5

Q7=7*3, 7*5, 7*7remove min = 3*3 = 9.

insert 3*3*3 in Q3, 3*3*5 into Q5, 3*3*7 into Q7

Q3=3*3*3

Q5=5*3, 5*5, 5*3*3

Q7=7*3, 7*5, 7*7,7*3*3

**Pseudocode:**

- initialize array and queues Q3, Q5 and Q7
- insert 1 into array
- insert 1*3 in Q3, 1*5 in Q5 and 1*7 in Q7
- let x be minimum element in Q3, Q5 and Q7.
- if x was found in

Q3 -> append 3*x, 5*x and 7*x in Q3, Q5 and Q7, remove x from Q3

Q5 -> append 5*x and 7*x in Q5 and Q7, remove x from Q5

Q7 -> append 7*x in Q7, remove x from Q7 - repeat 4–6 until we’ve found k elements

For more such questions, refer to: