Tricky Google interview question

Dijkstra derives an eloquent solution in "A Discipline of Programming". He attributes the problem to Hamming. Here is my implementation of Dijkstra’s solution.

int main()
{
    const int n = 20;       // Generate the first n numbers

    std::vector<int> v(n);
    v[0] = 1;

    int i2 = 0;             // Index for 2
    int i5 = 0;             // Index for 5

    int x2 = 2 * v[i2];     // Next two candidates
    int x5 = 5 * v[i5];

    for (int i = 1; i != n; ++i)
    {
        int m = std::min(x2, x5);
        std::cout << m << " ";
        v[i] = m;

        if (x2 == m)
        {
            ++i2;
            x2 = 2 * v[i2];
        }
        if (x5 == m)
        {
            ++i5;
            x5 = 5 * v[i5];
        }
    }

    std::cout << std::endl;
    return 0;
}

here is a more refined way of doing it (more refined than my previous answer, that is):

imagine the numbers are placed in a matrix:

     0    1    2    3    4    5   -- this is i
----------------------------------------------
0|   1    2    4    8   16   32
1|   5   10   20   40   80  160
2|  25   50  100  200  400  800
3| 125  250  500 1000 2000 ...
4| 625 1250 2500 5000 ...
j on the vertical

what you need to do is 'walk' this matrix, starting at (0,0). You also need to keep track of what your possible next moves are. When you start at (0,0) you only have two options: either (0,1) or (1,0): since the value of (0,1) is smaller, you choose that. then do the same for your next choice (0,2) or (1,0). So far, you have the following list: 1, 2, 4. Your next move is (1,0) since the value there is smaller than (0,3). However, you now have three choices for your next move: either (0,3), or (1,1), or (2,0).

You don't need the matrix to get the list, but you do need to keep track of all your choices (i.e. when you get to 125+, you will have 4 choices).