C ++で指定された桁の合計で数値（N以下）をカウントします

入力として数値と合計を含む文字列strが与えられます。目標は、桁の合計が合計に等しいstrまでの数値を見つけることです。

例を挙げて理解しましょう。

例

入力- N =” 110” sum =5

出力- 与えられた桁の合計でN以下の数の数は次のとおりです：7

説明- 桁の合計が5に等しい110までの数字は次のとおりです：-

5、14、23、32、41、50、104。

入力- N =” 1000” sum =3

出力- 与えられた桁の合計でN以下の数の数は次のとおりです：10

説明- 桁の合計が3に等しい1000までの数は：-

3、12、21、30、102、111、120、201、210、300。

以下のプログラムで使用されているアプローチは次のとおりです

このアプローチでは、動的計画法を使用して、数値とその桁の合計を配列arr [18][2][162]に格納します。ここで、18は最大18桁の数値、2は値0および1を表し、162は18桁すべてが9（18 * 9 =162）の場合に可能な最大合計を表します。

要素の値arr[i][j] [k]は、最初のi桁が考慮され、jが0または1である数のカウントを表します。 N.（Nが123でiが2の場合、2桁の数字が12以上であるかどうかを確認します。12に等しい場合、jは1になります。それ以外の場合、arr [i][j][kでjは0になります。 ]）。インデックスkは、arr [i][j][k]のi桁の合計になります。

i =Nの桁、k =入力合計の場合、結果は1、それ以外の場合は0になります。

次の桁（i + 1番目）を埋めるために、jをチェックします。 jが1の場合、i-1桁はNのi-1桁に等しいため、次の桁はNの0〜i+1番目の桁の値のみを使用して<=Nにすることができます。

jが0の場合、i-1桁の数値はNのi-1桁の数値よりも小さくなります。したがって、次の桁（i + 1番目）の位置に0から9までの任意の値を配置できますが、それでも以下になります。 N。

最後に、結果を最終カウントとして返します。

• 数値Nを表す文字列strを取得し、合計を桁の合計として取得します。
• 配列arr[18][2] [162]を取得し、memsetを使用して-1で初期化します。
• 関数count_digits（int i、bool check、int temp、int total、string str、int size）は、arr [] [] []を再帰的に埋め、最後に、指定されたN以下の数値のカウントを返します。数字の合計。
• 現在の桁数iがNの桁に等しく、現在の合計温度が入力合計合計に等しい場合は1を返し、それ以外の場合は0を返します。
• Take count =arr [i][check][temp]。 -1でない場合は、結果としてカウントを返します。
• 一時変数check_2（bool）とtemp_2を取得します。 （int）。
• forループを使用して0から9までの数字をトラバースし、チェックが1か0かを比較します。1の場合、現在の数字chをstr[i]と比較します。それより大きい場合は、ループを解除します（何もしません）。
• check_2=チェックを設定|| ch
• 現在の合計としてtemp_2=temp +（ch-'0'）を設定します。
• count_digits（i + 1、check_2、temp_2、total、str、size）を追加して、桁の合計を再帰的に計算するためにカウントします。
• 最後に結果としてカウントを返します。

例

#include <bits/stdc++.h>
using namespace std;
int arr[18][2][162];
int count_digits(int i, bool check, int temp, int total, ing str, int size) {
   if (i == size) {
      if (temp == total) {
         return 1;
      } else {
         return 0;
      }
   }
   int count = arr[i][check][temp];
   if (count != -1) {
      return count;
   }
   count = 0;
   bool check_2;
   int temp_2;
   for (char ch = '0'; ch <= '9'; ch++) {
      if (!check) {
         if (ch > str[i]) {
            break;
         }
      }
      check_2 = check || ch < str[i];
      temp_2 = temp + (ch - '0');
      count += count_digits(i + 1, check_2, temp_2, total, str, size);
   }
   return count;
}
int main() {
   string str = "1101";
   int size = str.size();
   int total = 5;
   memset(arr, -1, sizeof(arr));
   cout << "Count of numbers smaller than or equal to N with given digit sum are: " << count_digits(0, 0, 0, total, str, size);
   return 0;
}

上記のコードを実行すると、次の出力が生成されます-

出力

Count of numbers smaller than or equal to N with given digit sum are: 26