Googleの入社試験(非公式)にチャレンジしてみたで、チャレンジしたGoogleの入社試験(非公式)。
久しぶりに見直してみたら、間違ったソースコードだったので修正しました。

さらに、ソースを見ていると、長ったらしくてイライラしたので書き直すことにしてみました。

とりあえず、以下が問題文。

▼問題文

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

前回のソースは色々と無駄だらけなので、2番目に大きいnを探すだけに書き直してしまいます。

とりあえず、まとめてソースを書いちゃいます。

class GoogleTest {
    private $anw;        // 1.答えを格納するプライベート変数

    /**
     * 答えを返す
     *
     * @param    $search     int    検索する値を整数値で指定
     * @param    $start      int    検索を開始する値を整数値で指定
     * @param    $cnt        int    検索を開始する値までに必要な$searchの数を整数値で指定
     * return    int    『f(n)=n』となるような、2番目に大きいnを返す
     */
    public function getAnw() {
        // 2.答えがセットされていない場合、nを求める。
        // 3.f(1)=1になる事は分かっているので、2から数える
        if(!$this->anw) $this->setAnw(2, 1);

        return $this->anw;
    }

    /**
     * 引数nの中にある「1」の数を返す
     *
     * @param    $n        int    検索を開始する値を整数値で指定
     * @param    $count    int    0から$nの間の全ての数を書くのに必要とされる「1」の数を整数値で指定
     */
    public function setAnw($n, $count) {
        $count += substr_count($n, 1);

        if($n == $count) {
            // 4.答えを変数に格納する。
            $this->anw = $n;
        } else {
            // 5.再帰でもう一度計算する
            $this->setAnw($n+1, $count);
        }
    }
}

$gT = new GoogleTest();
echo $gT->getAnw();

【ソースコードの説明】

ざっとソースを説明します。

1.まずは答えを格納する変数を用意します。

2.答えが変数に格納されていない場合、答えを求めます。

3.『f(1) = 1』となるのは分かっているので、2からカウントします。
この時、1を書くのに必要な1の数は1なので、第2引数には1を指定します。
(文字にするとややこしいですね。。。)

4.nを書くのに必要な1の数がnと等しくなった場合、答えを変数に格納します。

5.nを書くのに必要な1の数がnと等しくない場合、再帰処理を行います。

これで終了です。
前回より見やすいソースになったと思います（たぶん・・・）

このままじゃ、0からnの間の全ての数を書くのに必要とされる「1」の数がnと等しい2番目に大きいnしか求めれないのでダメダメな感じですけど・・・
とりあえず、ソースも短くなったし、実行時間も早くなったので、よしとしておきます><