C++で数字dが正確にK回出現する範囲内の数値の数

変数から始まり、たとえば開始から変数の終わりまでの整数範囲と、変数kおよびdが与えられます。タスクは、dが正確にk回発生するような範囲の桁数dを計算することです。

例

入力- int start =10、int end =100、d =4、K =2

出力- 数字dが正確にK回出現する範囲内の数の数は次のとおりです：1

説明- 範囲は10から100までです。したがって、数字d、つまり4の可能な数字は、正確にkで発生します。つまり、2回は44であるため、カウントは1です。

入力- int start =10、end =100、d =6、m =1

出力- 数字dが正確にK回出現する範囲内の数の数は次のとおりです：1

説明- 範囲は10から100までです。したがって、数字d、つまり4の可能な数字は、正確にkで発生します。つまり、1回は16、26、36、46、56、76、86、および96であるため、カウントは8になります。 66はk回以上発生しているとは考えないでください。

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

• 変数の開始から変数の終了までの整数の範囲を作成し、変数dとkを宣言して、値を入力します。さらに処理するためにデータを関数に渡します。
• ベクトル型の変数を作成します。たとえばvecです。
• 変数内の値である値が開始するまでループを開始します。ここで、while内で、値をval％10としてベクトルにプッシュし、valをval/10として設定します。
• vec.begin（）とvec.end（）を引数として渡して、STLの逆関数を呼び出します。
• memsetを使用して、配列の値を-1に設定します。
• set_total（0、0、0、vec）を返します。これは、位置dが偶数で、mで割り切れるかどうかをチェックする関数です。
• set_total関数内-：
  • IFの場所がベクトルのサイズと等しいことを確認してから、IF temp =kを確認してから、1を返すか0を返します。
  • arr [place] [temp] [val] [rem]が-1に等しくないかどうかを確認し、arr [place] [temp][val][rem]の値を返します。
  • 結果を格納するための変数カウントを宣言します。
  • 変数temp_2を宣言し、valが1に等しい場合は9に設定します。ELSEはvec[place]で設定します。
  • temp_2までiから0までループFORを開始し、iがdに等しいかどうかを確認してから、dノートが0に等しいかどうかを確認するか、dが0であり、rem =1であるかどうかを確認し、合計を1ずつ増やします。
  • 変数をtemp_2として宣言し、valに設定します
  • ifiがvec[place]未満であることを確認してから、temp_2を1に設定します
  • 関数set_totalの再帰呼び出しでカウントを設定します
  • return arr [place] [temp] [val]=count。

例

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

const int MAX = 20;
int arr[MAX][MAX][2][2];
int d, K;

int set_total(int place, int temp, int val, int rem, vector < int > vec) {
   if (place == vec.size()) {
      if (temp == K) {
         return 1;
      }
      return 0;
   }
   if (arr[place][temp][val][rem] != -1) {
      return arr[place][temp][val][rem];
   }
   int count = 0;
   int temp_2 = (val ? 9 : vec[place]);

   for (int i = 0; i <= temp_2; i++) {
      int total = temp;
      if (i == d) {
         if (d != 0 || (!d && rem)) {
            total++;
         }
      }
      int total_2 = val;
      if (i < vec[place]) {
         total_2 = 1;
      }
      count += set_total(place + 1, total, total_2, rem || (i != 0), vec);
   }
   return arr[place][temp][val][rem] = count;
}

int occurrence_d(int val) {
   vector < int > vec;
   while (val) {
      vec.push_back(val % 10);
      val = val / 10;
   }
   reverse(vec.begin(), vec.end());
   memset(arr, -1, sizeof(arr));
   return set_total(0, 0, 0, 0, vec);
}
int main() {
   int start = 10;
   int end = 100;
   d = 4, K = 2;
   int count = occurrence_d(end) - occurrence_d(start - 1);
   cout << "Count of Numbers in a Range where digit d occurs exactly K times are: " << count;
   return 0;
}

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

出力

Count of Numbers in a Range where digit d occurs exactly K times are: 1