[Java] Generate the K-th number made only of primes 3, 5, 7

Generate the K-th number made only of primes 3, 5, 7.

Expected results up to K = 15: 1, 3, 5, 7, 9, 15, 21, 25, 27, 35, 45, 49, 63, 75, 81

This exercise is one of those that once the solution is known it's extremely easy but getting to the optimal solution requires work.

An initial suboptimal idea could be to start with a queue and placing only 1 in it.

Then execute some iterations where the top of the queue is polled, multiplied by 3,5,7 and then all results are added back to the queue, including the polled value.

We need to track generated values to avoid duplicating them. After some iterations, sort the queue, then poll until the k-th value is reached.

However the numbers generated this way quickly stray from the natural ordering so we end up generating more numbers that we need to get the actual solution.

After a long examination and paper examples (try drawing a matrix that expands with each new generated value and keep generating until the solution is reached), we notice that the emerging pattern is:

• use a queue for 3s, 5s, 7s 
• take the smallest top from all queues
• multiply this value by 3,5,7 UNLESS it is bigger that the top of a queue, in which case we skip that queue, then push it back to the corresponding 3,5 or 7 queue
• stop at k-th iteration, the min value generated at that step is the answer

This uses O(N) time and space and most importantly stops as soon as a result is reached.

You can check my implementation of generateKth357 on my Gist along with some tests in GenerateKth357JTests.