Find the Kth least number for expression (2^x)*(3^y)*(5^z)

Question

In the expression

2^x * 3^y * 5^z

The x, y and z can take non negative integer value (>=0).

So the function would generate a series of number 1,2,3,4,5,6,8,9,10,12,15,16....

• I have a brute force solution.
• I would basically iterate in a loop starting with 1 and in each iteration I would find if the current number factors are only from the set of 2,3 or 5.

What I would like to have is an elegant algorithm.

This is an interview question.

Answer 1

This can be solved using a priority queue, where you store triplets (x, y, z) sorted by the key 2^x3^y5^z.

1. Start with only the triplet (0, 0, 0) in the queue.

2. Remove the triplet (x, y, z) with the smallest key from the queue.

3. Insert the three triplets (x+1, y, z), (x, y+1, z) and (x, y, z+1) in the queue. Make sure you don't insert anything that was already there.

4. Repeat from step 2 until you've removed k triplets. The last one removed is your answer.

In effect, this becomes a sorted traversal of this directed acyclic graph. (First three levels shown here, the actual graph is of course infinite).