[解決済み] Googleの面接でのトリッキーな質問

質問内容

私の友人が就職の面接を受けています。面接の質問のひとつに考えさせられるものがあり、フィードバックが欲しいのです。

次の式が与えられたとき、出力がソートされるように i と j を反復する（最適な）解を求めよ。

2^i * 5^j

つまり、最初の数回はこんな感じでしょうか。

2^0 * 5^0 = 1
2^1 * 5^0 = 2
2^2 * 5^0 = 4
2^0 * 5^1 = 5
2^3 * 5^0 = 8
2^1 * 5^1 = 10
2^4 * 5^0 = 16
2^2 * 5^1 = 20
2^0 * 5^2 = 25

試行錯誤の結果、パターンが見当たりません。どう思いますか？

解決方法は？

Dijkstraは、"A Discipline of Programming"で雄弁な解決策を導き出しています。彼は、この問題をハミングに起因すると考えている。 以下は、Dijkstraの解決策を私が実装したものである。

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;
}