指定した数字根を持つ範囲内の数を効率的に見つけるC++プログラム

数字根（デジタルルート）とは、ある数の各桁の合計を求め、その結果が1桁になったときの値のことです。このチュートリアルでは、数の範囲と1桁の整数Xが与えられ、その範囲内で数字根がXと一致する数の個数を数える問題について解説します。

入力: l = 13, r = 25, X = 4
出力: 2
説明: 範囲(13, 25)内で桁の合計が4になる数は13と22の2つです。

入力: l = 11, r = 57
出力: 6

解法のアプローチ

単純なアプローチ

最もシンプルな方法は、lからrまでのすべての数を順番に走査し、それぞれの桁の合計がXと一致するかどうかを確認することです。しかし、この方法では範囲内の総数をNとすると、O(N)の時間計算量が必要となり、範囲が大きい場合には非効率になります。

効率的なアプローチ

ここで重要になるのが、数字根の数学的な性質です。任意の数の桁の合計は常に「num % 9」の結果と等しく、余りが0になる場合は9となります。したがって、X = 9が与えられた場合は、あらかじめ0に置き換えて処理します。

効率的に個数を求めるには、範囲全体を9個ずつのグループに分割します。すると、各グループには必ず1つだけ「num % 9 = X」を満たす数が存在することが保証されます。そのため、グループの数だけ答えに加算できます。その後、グループに含まれなかった端数の数については、1つずつ個別に条件を満たすかどうかを確認します。

実装例

上記アプローチのC++コード

#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int main(){
    int l = 13;
    int r = 25;
    int X = 4;
    if (X == 9) X = 0;
    // 範囲内のすべての数をカウント
    int total = r - l + 1;
    // 数を最大9個ずつのグループに分割
    int groups = total / 9;
    // Nグループあれば、mod 9がXと等しい数はN個存在する
    int result = groups;
    // グループに含まれない残りの数を確認
    int left_out = total % 9;
    // 残りの各数について条件を個別にチェック
    for (int i = r; i > r - left_out; i--) {
        int rem = i % 9;
        if (rem == X)
            result++;
    }
    cout << "Total Numbers in a Range( l, r ) with given Digital Root(X) are: " << result;
    return 0;
}

出力

Total Numbers in a Range( l, r ) with given Digital Root(X) are: 2

まとめ

このチュートリアルでは、数の範囲と目標となる数字根Xが与えられたとき、その範囲内で数字根がXと一致する数の個数を求める問題を取り上げました。全数を走査する単純なアプローチに加え、数を9個ずつのグループに分割することで高速化できる効率的なアプローチを紹介しました。

この性質を利用すれば、各グループに必ず1つ条件を満たす数が含まれるため、範囲が非常に大きい場合でも短時間で計算できます。紹介したC++プログラムのロジックは、C、Java、Pythonなどの他のプログラミング言語にも容易に応用できます。このチュートリアルが皆さんの学習のお役に立てば幸いです。