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

[非公認] Googleの入社試験

問題1
整数nが与えられたとき、0からnまでのすべての数を書くのに必要とされる｢1｣の数を
返す関数がある。例えば、f(13)=6になる。また、f(1)=1に注意。
f(n)=nとなるような、2番目に大きいnを求めなさい。

ソースコード。

#!/usr/bin/env python
# -*- coding:utf-8 -*-

def count_one(x):
    """ x を記述するのに必要な１の数をカウントする
    """
    num = 0 #val of 1
    for c in str(x):
        if(c=="1"): #文字列扱いのための2重引用符
            num +=1
    return num

def check_num2(x):
    counts = 1
    i = 1
    while(i <= x):
        i+=1
        counts += count_one(i)
        if counts == i:
            print "matchng:",i
    return counts

if __name__=="__main__":
    print check_num2(1000000) #8桁までで一致する場合

計算実行。

% python2.7 google.py           
matchng: 199981
matchng: 199982
matchng: 199983
matchng: 199984
matchng: 199985
matchng: 199986
matchng: 199987
matchng: 199988
matchng: 199989
matchng: 199990
matchng: 200000
matchng: 200001
600003

@see:
@see: Googleの入社試験(非公式)にチャレンジしてみた | Yasigani-ni Blog