指定範囲内で数字dが出現する回数を数えるアルゴリズムとC++実装

問題の概要

0〜9のいずれかの整数 d と、2つの正整数 low・high（それぞれ下限・上限）が与えられます。求めたいのは、low 以上 high 以下のすべての整数を並べたときに、数字 d が合計で何回現れるかです（両端の値も含みます）。

例として、d = 1、low = 1、high = 13 という入力を考えてみましょう。この場合の出力は 6 になります。1, 10, 11, 12, 13 の中で数字「1」は 1回＋1回＋2回＋1回＋1回＝計6回現れるためです。

解法のアプローチ

low から high までの数を1つずつ調べる方法では、範囲が大きくなると計算量が膨大になってしまいます。そこで、「1 から n までの整数に数字 x が現れる回数」を返す関数 f(x, n) を用意し、
f(d, high) − f(d, low − 1)
という差分によって、範囲内の出現回数を効率的に求めます。

関数 f(x, n) のロジック

n を上の桁から順に分解しながら、各位（1の位・10の位・100の位…）ごとに数字 x の出現回数を累積していきます。手順は以下の通りです。

• ret := 0 で初期化する
• m を 1 → 10 → 100 → … と10倍ずつ増やしながら、m ≤ n の間、次を繰り返す
  • a := n ÷ m（切り捨て除算：注目している位より上の部分）
  • b := n mod m（注目している位より下の部分）
  • z := a mod 10（現在注目している位の桁の値）
  • z > x のとき：ret += ((a ÷ 10) + 1) × m
  • z ＝ x のとき：ret += (a ÷ 10) × m + (b + 1)
  • それ以外のとき：ret += (a ÷ 10) × m
  • x ＝ 0 の場合は、先頭に来る余分な「0」を除外するため ret -= m
• ループ終了後、ret を返す

さらに、整数の桁数を返す補助関数 digitCount(x) も定義します。こちらは x を10で割り続け、割った回数を数えるだけのシンプルな実装です。

C++による実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int digitCount(int x){
        int ret = 0;
        while (x) {
            ret++;
            x /= 10;
        }
        return ret;
    }
    int zero(int n){
        int ret = 0;
        int x = 0;
        if (n == 0)
        return 1;
        for (int m = 1; m <= n; m *= 10) {
            int a = n / m;
            int b = n % m;
            int z = a % 10;
            if (digitCount(m) == digitCount(n))
            break;
            if (z > x) {
                ret += ((a / 10) + 1) * m;
            }
            else if (z == x) {
                ret += (a / 10) * m + (b + 1);
            } else {
                ret += (a / 10) * m;
            }
            cout << ret << endl;
        }
        return ret;
    }
    int f(int x, int n){
        int ret = 0;
        for (int m = 1; m <= n; m *= 10) {
            int a = n / m;
            int b = n % m;
            int z = a % 10;
            if (z > x) {
                ret += ((a / 10) + 1) * m;
            }
            else if (z == x) {
                ret += (a / 10) * m + (b + 1);
            } else {
                ret += (a / 10) * m;
            }
            if (x == 0) {
                ret -= m;
            }
        }
        return ret;
    }
    int digitsCount(int d, int low, int high){
        return f(d, high) - f(d, low - 1);
    }
};
main(){
    Solution ob;
    cout << (ob.digitsCount(1,1,13));
}

入力

1, 1, 13

出力

6

計算量について

n の桁数を k とおくと、f(x, n) は各桁を一度ずつ処理するだけでよいため、時間計算量は O(k)、すなわち O(log n) となります。low〜high の差が非常に大きい場合でも、桁数に比例した回数のループで済むため、高速に動作するのが大きなメリットです。