Google入社試験 - 解答編

※ このブログでは「10の5乗」のことを「10**5」と表記します(Python風)。


n以下の自然数に"1"が出てくる回数をカウントする関数f(n)において、

f(n) = n

となる2番目に大きいnを求めよ、という問題で、
とりあえずf(n)をPythonで実装してみました。
長くなってしまうので、解答は気が向いたら別の日に書きます。


直感的に実装すると

def f(n):
    return sum(map(lambda x: str(x).count('1'), xrange(n + 1)))

という感じになりそうですが、これでは著しく遅いですね。
O(n**2)というオーダーなので遅いのも当然です。
こんな恥ずかしい実装をするわけにはいきません。


そこで、こんな実装をしてみました。(※)

def f(n):
    s = str(n)
    count = 0
    while len(s) > 1:
        d = int(s[0])
        if d == 1:
            count += int(s[1:])
            count += (len(s) - 1) * 10 ** (len(s) - 2) + 1
        elif 2 <= d:
            count += (d * (len(s) - 1) + 10) * 10 ** (len(s) - 2)
        s = s[1:]
    if 1 <= int(s[0]):
        count += 1
    return count

これはオーダーが「nを10進数で表した際の桁数」になるので、
すなわち O(logN) で計算できることになります。


では、プログラムの説明をしてみます。


まずは計算しやすいケースを考えてみましょう、ということで、

f(999...999)

を求めてみます。
例えば9が6個並んでいる場合、

000000
000001
000002
...
999997
999998
999999

という表を考えて、その中に現れる"1"の個数を考えれば一目瞭然ですね。
数字は

6[桁] * (10**6)[行] = 6 * (10**6) 個

あり、0から9までの10種類の数字が均等に存在するので

f(999999) = 6 * (10**6) / 10 = 6 * (10**5) 個

となります。


同様に考えれば、

f(10**k - 1) = k * (10**(k-1))     (k = 0,1,2...)

となります。
すなわち

f(10**k) = k * (10**(k-1)) + 1     (k = 0,1,2...)

です。


これで

f(10), f(100), f(1000), f(10000) ...

が簡単に求められるようになりました。


もう一歩進めて、

f(50), f(300), f(9000), f(40000) ...

などのような、

f(a * 10**k)     (a = 0,1,2...9, k = 1,2,3...)

を求めてみましょう。


わかりやすさのために f(3000) を求めてみます。
まず、

g(n) = 自然数nに含まれる"1"の数

と定義します。つまり

f(n) = g(1) + g(2) + g(3) + ... + g(n)

ということです。

f(3000) = f(999) + g(1000) + g(1001) + ...
          + g(1999) + g(2000) + ... + g(2999) + g(3000)

となります。
これを4つのブロックにわけて、

f(3000) = f(999)                     --- (1)
          + g(1000) + ... + g(1999)  --- (2)
          + g(2000) + ... + g(2999)  --- (3)
          + g(3000)                  --- (4)

とします。
(1)はすでに計算済みで、f(999) = 3 * 10**(3-1) = 300 です。
(2)は g(000) + g(001) + ... + g(999) に 1000 を足したものなので、f(999) + 1000 = 1300 です。
(3)は g(000) + g(001) + ... + g(999) に等しいので、f(999) = 300 です。
(4)は 0 ですので、

f(3000) = 300 + 1300 + 300 = 1900

を簡単に求めることができます。


同様に考えると、

f(a * 10**k) = 
  (i) a == 1 の場合、
      k * 10**(k-1) + 1
  (ii) a >= 2 の場合、
      k * 10**(k-1) + 10**k + (a-1) * k * 10**(k-1)
      = (a * k + 10) * 10**(k-1)
  (iii) a == 0 の場合、
      当然 0
ただし k = 1,2,3...

となります。


これがわかれば f(ABCD) を求めることも簡単です。
(ここで A,B,C,D は各桁の数字であるとします。0から9のいずれかです。)

(i) A = 1の場合、
  f(ABCD) = f(1BCD)
          = f(1000) + BCD + f(BCD)
(ii) A >= 2の場合、
  f(ABCD) = f(A000) + f(BCD)

よって、再帰的に定義すれば、

def a10k(a, k):
    """returns f(a * 10 ** k)"""
    if a == 1:
        return k * 10 ** (k - 1) + 1
    elif a >= 2:
        return (a * k + 10) * 10 ** (k - 1)
    return 0

def f(n):
    s = str(n)
    d = int(s[0])
    if len(s) == 1:
        if d == 0:
            return 0
        return 1
    if d == 1:
        return a10k(d, len(s) - 1) + int(s[1:]) + f(int(s[1:]))
    elif d >= 2:
        return a10k(d, len(s) - 1) + f(int(s[1:]))

となり、これを再帰を使わずに実装したのが(※)のコードです。


これを使って確認しながら解答を求める…のはまたいずれ。
Googleの入社試験って面白いですね。


[非公認] Googleの入社試験

[非公認] Googleの入社試験