読者です 読者をやめる 読者になる 読者になる

uokadaの見逃し三振は嫌いです

ここで述べられていることは私の個人的な意見に基づくものであり、私が所属する組織には一切の関係はありません。

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

[非公認] 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 を記述するのに必要な1の数をカウントする
    """
    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