【C++】数値とその桁の合計との差がL以上となる数の個数を二分探索で求める方法

問題概要

整数 N と L が与えられます。1 以上 N 以下の数のうち、「その数自身から各桁の数字の合計を引いた差」が L 以上となる数の個数を求めるのが目的です。

例えば、N=23、L=10 の場合、条件を満たす数は 4 個になります。

• 23 - (2+3) = 18
• 22 - (2+2) = 18
• 21 - (2+1) = 18
• 20 - (2+0) = 18

これらの数はいずれも条件を満たしています。一方、19 - (1+9) = 9 となり L 未満であるため、19 以下の数(18、17、…、1)は条件を満たしません。

入力例と出力例

入力: N=30、L=19
出力: 1
説明: 条件を満たすのは 30 のみです。30 - (3+0) = 27 > 19 となるためです。

入力: N=123330、L=5466
出力: 6841

アルゴリズムの考え方

この問題の鍵となるのは、f(x) = x - (x の各桁の合計) という値が、x が増加しても減少しない(単調非減少である)という性質です。そのため、二分探索を使えば「条件を満たす最小の数」を効率的に見つけられます。

ある数が条件を満たしていれば、それより大きい数もすべて条件を満たします。したがって、条件を満たす最小の数が m であれば、答えは N - m + 1 として求められます。

また、二分探索の途中で中央値 temp が条件を満たす場合は、temp から探索範囲の上端までの数はすべて条件を満たすため、end - temp + 1 をカウントに加算できます。

解法の手順

• num と L を long long 型の変数として受け取ります。
• 関数 Digit_sum(LL num) は、数値 num を受け取り、その各桁の合計を返します。初期値 total=0 とし、while ループで num % 10 を total に加算しながら num を 10 で割る操作を、num > 0 の間繰り返します。
• 関数 Less_than_L(LL num, LL L) は、数値とその桁の合計との差が L 以上となる数の個数を返します。
• count の初期値を 0、start=1、end=num とし、while ループで二分探索を実装します。
• 中央値を temp=(start+end)/2 として計算します。
• temp とその桁和の差が L 以上であれば、temp より大きい数もすべて条件を満たすため、num-temp+1 を count に設定し、end=temp-1 として探索範囲を左半分に狭めます。
• 条件を満たさない場合は、start=temp+1 として探索範囲を右半分に狭めます。
• 二分探索が終了すると、count には差が L 以上となる数の個数が格納されています。
• count を結果として返します。

計算量について見てみましょう。二分探索は O(log N)、各ステップでの桁和計算は O(log N) であるため、全体の計算量は O((log N)²) となります。1 から N までを順番に調べる O(N) の方法に比べて、大幅な高速化が可能です。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

// 各桁の合計を求める関数
int Digit_sum(LL num){
    LL total = 0;
    while (num > 0){
        total += num % 10;
        num = num / 10;
    }
    return total;
}

// 数値とその桁の合計との差が L 以上となる数の個数を求める関数
LL Less_than_L(LL num, LL L){
    LL count = 0;
    LL start = 1;
    LL end = num;
    while (start <= end){
        LL temp = (end + start) / 2;
        LL diff = temp - Digit_sum(temp);
        if (diff >= L){
            // temp 以上の数はすべて条件を満たす
            count = num - temp + 1;
            end = temp - 1;
        }
        else{
            start = temp + 1;
        }
    }
    return count;
}

int main(){
    LL num = 234516;
    LL L = 235;
    cout << "数とその桁の合計との差がL以上となる数の個数: " << Less_than_L(num, L);
    return 0;
}

実行結果

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

数とその桁の合計との差がL以上となる数の個数: 234267

まとめ

数値とその各桁の合計との差は単調に増加していく性質を持つため、この問題では二分探索が非常に有効です。全件を線形に走査する代わりに O((log N)²) で解けるため、N が非常に大きい場合でも高速に動作する点が大きな魅力といえます。