A straightforward solution to the 2-3-5 problem
It's time to add one more to the list of solutions to the 2-3-5 problem. This solution recasts Dijkstra's original solution, with one significant change: Dijkstra appended numbers to arrays and then kept track of an index in each array that indicated where to start looking. Instead of doing that, I'm going to use the C++ queue class.
The basic idea behind the solution is to follow the description of the problem: 1 is a member of the sequence, and if n is a member, so are 2n, 3n, and 5n. We will therefore start out with 1 as the first known element of our sequence; and each time we have figured out an element of the sequence, we shall multiply that element by 2, 3, and 5, respectively, and append those products to three queues.
The next element in the sequence will then be the smallest value in any of those arrays. Because the program will produce elements of the sequence in ascending order, the queues themselves will also be in ascending order, thereby guaranteeing that the smallest element in each queue is also the first.
In other words, we begin our program as follows:
queue q2, q3, q5;
int n = 1;
We have said that the current element of the sequence has the value 1, and that so far we know nothing else about the sequence. We can print this element:
cout << n << endl;
after which we must figure out how to set n to the value of the next element in the sequence.
We do this figuring in three steps. The first step is to push 2n, 3n, and 5n onto their respective queues:
q2.push(n * 2);
q3.push(n * 3);
q5.push(n * 5);
At this point, we have guaranteed that each of the queues is nonempty. Moreover, because we are generating elements of the sequence in strictly ascending order, each queue will also be in ascending order.
However, there is no guarantee that a value will not appear in more than one queue! For example, after we generate the value 2, we will push 10 (2 * 5) onto q5. Moreover, after we generate the value 5, we will push 10 (5 * 2) onto q2. So even though any given value will appear no more than once in any one queue, it may appear in more than one queue.
Our second step, then, will be to determine the smallest value at the head of any of the queues. This value will be the next value of n:
n = min(q2.front(), min(q3.front(), q5.front()));
The use of q2.front(), q3.front(), and q5.front() without checking whether the queues are empty is justified by the fact that we just pushed a value onto the end of each queue. Therefore, it is impossible for any of them to be empty at this point.
Our third and final step is to remove the value n from each queue that it heads:
if (n == q2.front())
if (n == q3.front())
if (n == q5.front())
How fast does this program run? Each time we generate an element, we push three values onto queues and remove no more than three values from queues. Therefore, the program executes a number of operations that is no worse than linear in the number of values computed.