Googleの入社試験(非公式)にチャレンジしてみた

プログラマーを目指す前の話なんですが、大阪の『ちちんぷいぷい』という番組で『Googleの入社試験を紹介』というコーナーを見たことがありました。
その時は、「この人たちの頭の中はどうなっているんだ・・・」と思うだけだったのですが、僕も今ではプログラムを嗜む身。
1問ぐらいは解いてやろうと思い、ググってみると面白そうな問題がありました。

▼問題文
整数nが与えられたとき、0からnの間の全ての数を書くのに必要とされる「1」の数を返す関数があります。たとえば、『f(13)=6』になります。また、『f(1)=1』に注意。『f(n)=n』となるような、2番目に大きいnを求めなさい。

面白そうな問題でしょ?
さっそくチャレンジしてみましょ。
僕は、PHPerなのでPHPで解いてみます。


2012/01/06  追記

ソースコードを間違っていました・・・。
修正版に書き直しています。


▼以下、問題にチャレンジ


2番目に大きいnってことは、『f(1)=1』の次の整数nを探せばクリア(って事ですよね・・・?)
とりあえず、関数f(n)を作成しない事には答え合わせもできないので、先に関数f(n)を作っちゃいます。

/**
 * 引数nの中にある「1」の数を返す
 *
 * $n		int	整数値を指定
 * return	int	0からnの間の全ての数を書くのに必要とされる「1」の数を返す
 */
function f($n) {
    $count = 0;

    for($i = 1; $i

substr_countを使って、1の文字を数え、出現回数を返すだけの簡単な関数です。
これで、「0からnの間の全ての数を書くのに必要とされる1の数」を数える事ができました。
あとは、「2番目に大きいn」を探すだけです。
関数f(n)を使って総当りで調べてもいいんですが、さすがにそれはスマートじゃないし、タイムオーバーしちゃう。
ってわけで、こんな関数を作りました。

/**
 * 引数$startから引数$endの中にある「1」の数を返す
 *
 * $start	int	1の出現回数を調べる範囲の開始値を整数値で指定
 * $end		int	1の出現回数を調べる範囲の終了値を整数値で指定
 * return	int	$startから$endの間の全ての数を書くのに必要とされる「1」の数を返す
 */
function fEx($start, $end) {
    $count = 0;

    for(; $start

1~10までの数を書くのに必要とされる「1」の数を返す関数です。
この関数で、「1」を数える範囲を小分けにします。
次は、「2番目に大きいn」を探す関数を作ります。

/**
 * 0からnの間の全ての数を書くのに必要とされる「1」の数の2番目に大きいnを返す。
 *
 * return	int	2番目に大きいnを返す。
 */

function main() {
    $allCnt = 0;	// 『1』の数
    $start  = 1;	// 『1』の数を数える開始範囲
    $end    = 10;	// 『1』の数を数える終了範囲
    $i      = 0;	// ループ回数をカウント(ログ用のオマケ)

    // 1・結果が見つかるまで無限ループを開始
    while(true) {
        // 2・$startから$endの範囲の『1』の数を数え、前回の検索範囲の『1』の数と足す
        $allCnt += $this->fEx($start, $end);

        /* 3・「f(n) = n」となるということは、検索範囲の中に答えがあるはず(答えが「n == 1」なら1~10の間に答えがある)なので、検索範囲の中に『1』の数があればチェックする
         *    「f(1) = 1」は除外
         */
        if($allCnt >= $start && $allCnt <= $end && $start != 1) {
            // 4・開始範囲から1づつ足して確認したいため、開始の数を代入
            // 5・「f(n) = n」になれば終了。falseなら終了範囲を超えるまで1を足す
            for($tmp = $start; $tmp <= $end; $tmp++) {
                if(($this->f($tmp) == $tmp)) {
                    echo "
ヒットしました。    答えは、『 $tmp 』です。"; return $tmp; } } // 6・ヒットしなかったので、ログを出力。 $i++; echo "『 $start ~ $end 』の間ではヒットしませんでした。$i 回目のループに入ります
"; } // 7・3の条件にあてはまらなかったので、次の検索範囲を指定してループ再開 $start += 10; $end += 10; } }

【ソースコードの説明】


1・結果が見つかるまで無限ループを開始。


2・関数fEx($start, $end)を使って『1』の数を数え、前回検索した範囲の『1』の数と足す。


3・「f(n) = n」になるなら、検索した範囲の中にnがあるはずなので、『1』の数が検索範囲内ならチェック。
(f(1)=1になる事は分かっているので、$startが「1」の場合はチェックしません)


4・開始範囲から1づつ足して確認したいため、開始の数を代入
(2番目に大きい数なので、検索開始範囲から探した方が早いと思う)


5・「f(n) = n」になれば終了。falseなら終了範囲を超えるまで1を足す。


6・検索範囲内に答えがなければ、ログを出力。


7・『1』の数が検索範囲内になければ、次の検索範囲を指定してループを再開する。

これで、「2番目に大きいn」が見つかるはず・・・
んで、PHPを実行。


【実行結果】
『 11 ~ 20 』の間ではヒットしませんでした。1 回目のループに入ります
『 199911 ~ 199920 』の間ではヒットしませんでした。2 回目のループに入ります
『 199921 ~ 199930 』の間ではヒットしませんでした。3 回目のループに入ります
『 199931 ~ 199940 』の間ではヒットしませんでした。4 回目のループに入ります
『 199941 ~ 199950 』の間ではヒットしませんでした。5 回目のループに入ります
『 199951 ~ 199960 』の間ではヒットしませんでした。6 回目のループに入ります
『 199961 ~ 199970 』の間ではヒットしませんでした。7 回目のループに入ります
『 199971 ~ 199980 』の間ではヒットしませんでした。8 回目のループに入ります

ヒットしました。 答えは、『 199981 』です。

答え合わせに関数fで確認したところ、ちゃんと『f(n)=n』になってました^^
いや~。解けてよかった><
また問題にチャレンジしてみよ~。


追記
まあ、本当にこれで正解なのかは分かりませんが・・・。
「間違ってるよ」とか「無駄な処理してるよ」という方。ご指摘頂けたら嬉しいです。