C++で桁の合計が指定した合計に一致するn桁の数の個数を求める方法

正の整数として桁数と合計が与えられます。目的は、各桁の数字の合計が入力された合計と等しくなるようなd桁の数をすべて数えることです。なお、先頭に0が付く数(リーディングゼロを含む数)はd桁の数としては扱いません。

制約は、桁数が1〜100、合計が1〜500です。

例で理解しよう

例1

入力: digits = 3, digi_sum = 3

出力: 桁の合計が指定された合計に等しいn桁の数の個数:6

説明: 各桁の合計が3となる3桁の数は、次の6つです。

102、111、120、201、210、300

例2

入力: digits = 4, digi_sum = 2

出力: 桁の合計が指定された合計に等しいn桁の数の個数:4

説明: 各桁の合計が2となる4桁の数は、次の4つです。

1001、1010、1100、2000

プログラムで使用するアプローチ

このアプローチでは、最初のd桁の数から順番に走査し、桁の合計が指定された合計と一致する最初の数を見つけます。以降は、桁の合計が指定された合計を超えるまで9ずつ数を増やしながら調べます。桁の合計が入力の合計を超える数が見つかったら、その数を1増やして、再び合計が一致する次の数を探します。この処理を、d桁の最大の数に達するまで繰り返します。

• 桁数と桁の合計を入力として受け取ります。
• 関数digits_sum(int digits, int digi_sum)は、これら2つの入力値を受け取り、桁の合計が指定された合計に等しいn桁の数の個数を返します。
• カウントの初期値を0とします。
• 範囲の最初の数をLeft = pow(10, digits - 1)、最後の数をright = pow(10, digits) - 1とします(digits=2の場合は10〜99)。
• whileループを使って、leftからrightまで走査します。
• first = 0、last = i と初期化します。
• 各i(last)について、最下位桁(last % 10)をfirstに加算し、lastを10で割って次の反復に備えます。
• firstがdigi_sumと等しくなったらcountを1増やし、iに9を加算して次の反復へ進みます。
• それ以外の場合は、iを1増やします。
• すべてのループが終了した時点で、countには桁の合計がdigi_sumに等しい数の個数が格納されています。
• countを結果として返します。

サンプルコード

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

int digits_sum(int digits, int digi_sum) {
    int count = 0;
    int Left = pow(10, digits - 1);
    int right = pow(10, digits) - 1;
    int i = Left;
    while (i <= right) {
        int first = 0;
        int last = i;
        while (last != 0) {
            first = first + last % 10;
            last = last / 10;
        }
        if (first == digi_sum) {
            count++;
            i = i + 9;
        } else {
            i++;
        }
    }
    return count;
}
int main() {
    int digits = 5;
    int digi_sum = 7;
    cout << "桁の合計が指定された合計に等しいn桁の数の個数: " << digits_sum(digits, digi_sum);
    return 0;
}

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

出力

桁の合計が指定された合計に等しいn桁の数の個数: 5