Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

A straightforward solution to the 2-3-5 problem

January 18, 2009

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())
        q2.pop();
    if (n == q3.front())
        q3.pop();
    if (n == q5.front())
        q5.pop();

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.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video