151013

Ruby

Number of times k is used in writing out all the numbers 1 through n(5)

Number of times k is used in writing out all the numbers 1 through n(4)
の m = 10 のときの結果を眺めると、
1～9が平等、0が不遇
に見えるが、一般のnに対しては、
1, 2, … , 9
の順に優先されるのであろう。
さて、もう一度「非公認 Googleの入社試験」に載っていた問題について考えると、
ｆ を1の回数にしてくれているので、ｆ(n) = n が簡単に見つかるのである。
このことを実感するために、次のコードを実行してみよう。

# k > 0
def search(k, n)
  i = 0
  cnt = 0
  ary = [0]
  while i < n
    i += 1
    cnt += i.to_s.count(k.to_s)
    ary << i if i == cnt
  end
  ary
end

(1..9).each{|k| p search(k, 10 ** 8)}

# 以下検算用
def g(m, k, str, s)
  if s == 1
    return 0 if str.to_i < k
    return 1
  end
  a = str[0].to_i
  str1 = str[1..-1]
  if a < k
    b = 0
  elsif a == k
    b = 1 + str1.to_i(m)
  else
    b = m ** (s - 1)
  end
  return a * (s - 1) * m ** (s - 2) + b + g(m, k, str1, s - 1)
end

def g_total(m, n)
  s = n.to_s(m).size
  (n - m ** (s - 1) + 1) * s + ((s - 1) * m ** s - s * m ** (s - 1) + 1) / (m - 1)
end

def f(m, k, n)
  str = n.to_s(m)
  return g(m, k, str, str.size) if k > 0
  sum = 0
  (1..m - 1).each{|k0| sum += g(m, k0, str, str.size)}
  g_total(m, n) - sum
end

p f(10, 2, 28263827) == 28263827
p f(10, 2, 35000000) == 35000000

出力結果
[0, 1, 199981, 199982, 199983, 199984, 199985, 199986, 199987, 199988, 199989, 199990, 200000, 200001, 1599981, 1599982, 1599983, 1599984, 1599985, 1599986, 1599987, 1599988, 1599989, 1599990, 2600000, 2600001, 13199998, 35000000, 35000001, 35199981, 35199982, 35199983, 35199984, 35199985, 35199986, 35199987, 35199988, 35199989, 35199990, 35200000, 35200001]
[0, 28263827, 35000000]
[0]
[0]
[0]
[0]
[0]
[0]
[0]
true
true