C++で0からnまでの整数に含まれる「1」の出現回数を効率的に数える方法

問題概要

非負整数 n が与えられたとき、0 以上 n 以下のすべての整数に登場する数字「1」の合計出現回数を求める問題です。

たとえば入力が 15 の場合を考えてみましょう。「1」を含む数は [1, 10, 11, 12, 13, 14, 15] であり、これらに含まれる「1」は合計 8 個 です(11 には「1」が2個含まれる点に注意してください)。したがって出力は 8 となります。

解法のアプローチ

すべての数を1つずつ調べる方法では計算量が膨大になるため、ここでは桁ごとに「1」の出現回数を数える効率的な手法を採用します。1の位・10の位・100の位…と各桁の位置について、その桁に「1」が現れる回数を数学的に導出していきます。

具体的な手順は次のとおりです。

• ret := 0 として結果を初期化します。

• i := 1(1の位)から開始し、i <= n の間、i = i * 10 として桁をずらしながら繰り返します。

  • a := n / i(注目桁より上位の部分)、b := n mod i(注目桁より下位の部分)、x := a mod 10(現在注目している桁の数字)を求めます。

  • x == 1 の場合:
    ret = ret + (a / 10) * i + (b + 1)

  • x == 0 の場合:
    ret = ret + (a / 10) * i

  • それ以外(x >= 2)の場合:
    ret = ret + (a / 10 + 1) * i

• 最後に ret を返します。

なぜこの式が成り立つのか

ある桁に「1」が現れる回数は、「その桁より上位の部分」と「下位の部分」の組み合わせによって決まります。

• 注目桁が 0 のとき: 上位部分が 0 ~ (a/10 − 1) の範囲でのみ「1」が出現するため、(a / 10) * i 回となります。
• 注目桁が 1 のとき: 上位部分が a/10 の場合でも、下位部分が 0 ~ b の範囲で追加的に「1」が出現するため、(a / 10) * i + (b + 1) 回となります。
• 注目桁が 2 以上のとき: 上位部分が 0 ~ a/10 のすべての範囲で「1」が出現するため、(a / 10 + 1) * i 回となります。

C++による実装例

それでは、実際のコードを見て理解を深めましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int countDigitOne(int n) {
      int ret = 0;
      for(long long int i = 1; i <= n; i*= (long long int)10){
         int a = n / i;
         int b = n % i;
         int x = a % 10;
         if(x ==1){
            ret += (a / 10) * i + (b + 1);
         }
         else if(x == 0){
            ret += (a / 10) * i;
         } else {
            ret += (a / 10 + 1) *i;
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.countDigitOne(15));
}

入力

15

出力

8

計算量について

ループは n の桁数分だけしか回転しないため、時間計算量は O(log₁₀ n)、空間計算量は O(1) です。n が非常に大きな値であっても高速に動作するのが、このアルゴリズムの大きな利点です。