C++で数値とその桁の合計の差が特定の値より大きい数をカウントする方法

本記事では、2つの整数N（探索範囲 [1, N] を定義）とD（差のしきい値）が与えられたとき、「数値 − その桁の合計 > D」という条件を満たす数が範囲内にいくつあるかを求める方法を解説します。

解き方はシンプルです。1からNまでの数を順番に走査し、それぞれの数についてwhileループを使って桁の合計を計算します。その後、元の数と桁の合計の差がDより大きいかどうかを判定し、条件を満たしていればカウントを増やします。

具体例で理解しよう

例1

入力：

N=15 D=5

出力：

数値と桁の合計の差がDより大きい数: 6

説明：

10, 11, 12, 13, 14, 15 が条件を満たします。（10−1, 11−2, 12−3, 13−4, 14−5, 15−6）いずれも差は9であり、5より大きいためです。

例2

入力：

N=20 D=10

出力：

条件を満たすのは20のみ。20−2=18 > 10。

説明：

たとえば19の場合、19−(1+9)=9 となり、10以下のため条件を満たしません。同様に、1桁の数や小さい数は桁の合計との差が小さくなるため、ほとんどが条件外となります。

プログラムのアプローチ

• 整数NとDを受け取ります。

• 関数 digitSum(int n, int d) は、引数として受け取ったNとDをもとに、「（数値 − 桁の合計）> d」を満たす数の個数を返します。

• 条件を満たす数を数えるための変数 count を0で初期化します。

• 桁の合計を格納する変数 digsum を0で初期化します。

• forループを使って i=1 から i=n までの範囲を走査します。

• 各数 num=i に対して、whileループで num が0より大きい間、処理を繰り返します。

• digsum += num % 10 で最下位の桁を加算し、num = num / 10 として次の桁へ進みます。

• whileループを抜けたら、i − digsum > d が成り立つか判定します。真であれば count をインクリメントします。

• すべてのループが終わった時点で、count には条件を満たす数の総数が格納されています。

• count を結果として返します。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
int digitSum(int n, int d){
    int count = 0;
    int digsum = 0;
    for (int i = 1; i <= n; i++){
       int num=i;
       digsum=0;
       while(num>0){
          digsum+=num%10; //桁の合計を求める
          num=num/10;
       }
       if(i-digsum>d) //元の数はi          count++;
          //cout<<i<<" ";
       }
   }
   return count;
}
int main(){
   int N = 20;
   int D = 8;
   cout <<"数値と桁の合計の差が特定の値より大きい数: "<<digitSum(N,D);
   return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

数値と桁の合計の差が特定の値より大きい数: 11

計算量について

このアプローチの時間計算量は O(N × log₁₀N) です。各数の桁数は最大 log₁₀N 桁であるため、1からNまでの各数について桁の合計を求める処理が走査ごとに発生します。空間計算量は O(1) で、追加のデータ構造を必要としないシンプルな実装です。

Nが非常に大きい場合は効率化の余地がありますが、一般的な入力サイズであればこの素直な全走査方式で十分に高速に動作します。