C ++では、0を数字として、最大の「d」桁を含む正の整数をカウントします

桁数を表す数dが与えられます。目標は、0を桁とし、最大d桁の正の整数の数を見つけることです。少なくとも1つの0を含むすべての1桁、2桁、3桁….d桁の正の数を数えます。

最初に、少なくとも1つの0を持つd桁の数の数を見つけます。d=3としましょう。少なくとも1つの0で3桁の数字を作成するには、次の方法があります-

Here d1 can have 1 to 9 : 9 ways
d2 can have 0-9 : 10 ways
d3 can have 0-9 : 10 ways
Total numbers possible: 9 x 10 x 10 = 9 x 102
For d digits, count of numbers: 9 x 10d-1
For d digits, numbers without any 0 are : 9d
Total numbers having d digits with at least one 0 = 9 x 10d-1 - 9d = 9 x ( 10d-1 - 9d-1 )

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

入力 − d =4

出力 − 0を桁とし、最大の「d」桁を含む正の整数の数は− 2619

説明 −少なくとも1つの0を含むx桁の数字−

1 digit numbers : 0
2 digit numbers : 9
3 digit numbers : 171
4 digit numbers: 2439
Total= 9+171+2439 = 2619

入力 − d =1

出力 − 0を桁とし、最大の「d」桁を含む正の整数の数は− 0

説明 −1から9までの数字は数字として0を持ちません。

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

2つのアプローチを使用します。 forループを使用した最初の素朴なアプローチ。 1桁からd桁までのトラバースを開始し、上記の式を使用して数値を計算します。カウントに戻り値を追加します。

• 整数dを数字とします。

• 関数total_count（int d））は、桁数dを取り、少なくとも1つの0を持つd桁の数値のカウントを返します。

• temp =9 *（pow（10、d-1）--pow（9、d-1））;

  のような数値を計算します。

• 戻り温度。

• 関数maximum_d（int d）は、最大桁数dを取り、少なくとも1つの0を持つd桁までの数値のカウントを返します。

• 1桁の数字から始まり、2、というようにdまでループを使用してトラバースします。

• 各dについて、total_count（i）として数値を計算します。これを追加してカウントします。

• 最後に、合計数を取得します。

• 結果としてカウントを返します。

効率的なアプローチ

このアプローチでは、上記の計算で形成されたG.Pを観察して、カウントを計算します。

Solution is 9 x (10d-1 - 9d-1)
= 9 x (10d - 1)- 9 x (9d-1)
= 9 x (10i - 1) - 9 x (9i - 1) ( 1<=i<=d )
= g.p 1 - g.p 2
= 9x(10d-1)/(10-1) - 9x(9d-1)/(9-1)
= (10d-1)- (9/8)*(9d-1)

• dを最大桁数とします。

• 関数maximum_d（int d）は、最大桁数dを取り、少なくとも1つの0を持つd桁までの数値のカウントを返します。

• 上記の式を使用して、temp_1を9 *（（pow（10、d）-1）/ 9）として計算します。

• temp_2を9*（（pow（9、d）-1）/ 8）として計算します。

• count=temp_1--temp_2を設定します。

• 結果としてカウントを返します。

例（素朴なアプローチ）

#include<bits/stdc++.h>
using namespace std;
int total_count(int d){
   int temp = 9*(pow(10,d-1) - pow(9,d-1));
   return temp;
}
int maximum_d(int d){
   int count = 0;
   for (int i=1; i<=d; i++){
      count = count + total_count(i);
   }
   return count;
}
int main(){
   int d = 5;
   cout<<"Count of positive integers with 0 as a digit and maximum 'd' digits are: "<<maximum_d(d) << endl;
   return 0;
}

出力

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

Count of positive integers with 0 as a digit and maximum 'd' digits are: 33570

例（効率的なアプローチ）

#include<bits/stdc++.h>
using namespace std;
int maximum_d(int d){
   int temp_1 = 9*((pow(10,d)-1)/9);
   int temp_2 = 9*((pow(9,d)-1)/8);
   int count = temp_1 - temp_2;
   return count;
}
int main(){
   int d = 4;
   cout<<"Count of positive integers with 0 as a digit and maximum 'd' digits are: "<<maximum_d(d) << endl;
   return 0;
}

出力

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

Count of positive integers with 0 as a digit and maximum 'd' digits are: 2619