C++で数値にゼロ以外の数字がK個を超えない範囲内の数値の数

変数から始まり、変数の終わりまでの整数範囲と変数kが与えられます。タスクは、数値がゼロ以外の「k」を超えないように、範囲内の数値の数を計算することです。数字。

例

入力- int start =50、end =100、K =2;

出力- 数値にゼロ以外の数字がK個を超えない範囲内の数値の数は次のとおりです。50

説明- 範囲は50から100までで、kは2として与えられます。ご覧のとおり、50から100までのすべての数値は2桁の数値であるため、100という数値を除いて2桁を超えるゼロ桁を含めることはできません。 3桁の数字ですが、2つのゼロがそれ以下になるため、カウントは50になります。

入力- int start =50、end =100、K =1;

出力- 数値にゼロ以外のKを超えない範囲内の数値の数

数字は次のとおりです：5

説明- 範囲は50から100で始まり、kは1として与えられます。ご覧のとおり、50から100までのすべての数値は2桁の数値であるため、1以下の数値またはゼロ以外の桁としてのkは50です。 、60、70、80、および90であるため、カウントは5です。

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

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

例

#include <bits/stdc++.h>
using namespace std;
int arr[20][20][2];
int K;
int check_val(int place, int temp, int set_val, vector < int > vec) {
   if (place == vec.size()) {
      if (temp <= K) {
         return 1;
      }
      return 0;
   }
   if (arr[place][temp][set_val] != -1) {
      return arr[place][temp][set_val];
   }
   int count = 0;
   int val = (set_val ? 9 : vec[place]);
   for (int i = 0; i <= val; i++) {
      int temp_2 = temp;
      if (i != 0) {
         temp_2++;
      }
      int temp_3 = set_val;
      if (i < vec[place]) {
         temp_3 = 1;
      }
      count += check_val(place + 1, temp_2, temp_3, vec);
   }
   return arr[place][temp][set_val] = count;
}

int Not_more_k(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 check_val(0, 0, 0, vec);
}
int main() {
   int start = 50, end = 100;
   K = 2;
   int count = Not_more_k(end) - Not_more_k(start);
   cout << "Count of Numbers in Range where the number does not contain more than K non zero digits are: " << count;
   return 0;
}

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

出力

Count of Numbers in Range where the number does not contain more than K non zero digits are: 50