No Caffeine, No Life

プログラミング(主にPython)

CodeIQ: 「7」の数を数えよう

CodeIQで次のような問題が出題されていた:

 1からnまで連続する正の整数があります。

それらの中に、「7」がいくつあるかを数えてください。

 

【例】

n = 99とすると、

1 2 3 4 5 6 7 8 9 10

11 12 13 14 15 16 17 18 19 20

21 22 23 24 25 26 27 28 29 30

31 32 33 34 35 36 37 38 39 40

41 42 43 44 45 46 47 48 49 50

51 52 53 54 55 56 57 58 59 60

61 62 63 64 65 66 67 68 69 70

71 72 73 74 75 76 77 78 79 80

81 82 83 84 85 86 87 88 89 90

91 92 93 94 95 96 97 98 99

 

「7」を含む値は、

7 17 27 37 47 57 67 70 71 72 73 74 75 76 77 78 79 87 97

の19個ですが、77には「7」が2つ含まれています。

ですので、「7」の数は19個ではなく、20個と答えてください。なお、nは32bit整数に収まるものとします。

 素直に、与えられたnに対して1つずつ'7'がいくつあるかをカウントしていくやり方を取ってみる:

gist.github.com

nが小さいうちならこれでもいいのだけれど、テストケースではn = 10億ほどであり、このままだと恐ろしく時間がかかる(タイムリミットが1秒と決まっていたのに対し、n = 1.0 x 10^8で30秒ほどかかった)。そのため、別の方法を考える必要がある。

 

 上のプログラムを用いてもいいのだけれど、まず気が付かなくてはいけないのは、キリのいい数、たとえば100とか1000とか、までに7はいくつ入っているのか、ということだ。1行目に、探索する数の上限値(例:100とあれば1から100まで、ということ)を、2行目に、含まれる7の個数を列挙するとこうなる:

 max      count

100         20
200         40
300         60
400         80
500       100
600       120
700       141
800       260
900       280
1000     300
2000     600
3000     900
4000     1200
5000     1500
6000     1800
7000     2101
8000     3400
9000     3700
10000   4000

ここで気づくことは、

  • 100-1000までは20個ずつ、1000-10000までは300個ずつ増えていくこと。
  • 最高位の数字が1~6までと、7~9までとは様子がちょっと違うこと
  • 最高位の数字が7のとき、 6の時と比べて+1があること
  • 最高位の数字が8のとき、7の時と比べて、100もしくは1000増えていること(ただし、+1を無視)。

 ちょっと考えてみると、これは確かにもっともな話で、

  • 最初の100個(00から99まで)の数値を横に並べれば、2桁 x 100 = 200個の数字が並ぶ。そこに、0から9までの10個の数字が一様に発生するはずなので、7の数は20個(そこに、100を考えても7は含まれていないので結論は変わらない)。同様に、最初の1000個(000から999まで)の数値を横に並べれば、3桁 x 1000 = 3000個の数字が並ぶ。そこに、0から9までの10個の数字が一様に発生するはずなので、7の数は300個。
  • 7が入るときは、700, 7000を含める必要があるので+1。
  • 800, 8000までのとき、701から799、7001から7999までの100個、1000個を加える必要がある。

そこで、最高桁からみて、順に区切って何個あるかを調べていけばよい。そうすると、次のようなプログラムになる:

gist.github.com

これで求めると一瞬で答えが出る。

 

広告を非表示にする