C++でL以上の数とその桁の合計の差が生じるような数の数

数Nと別の数Lが与えられます。目標は、数自体とその桁の合計がL以上である1からNまでの数を見つけることです。

N =23、L =10の場合、そのような数の数は4になります。

23-（2 + 3）=18、22-（2 + 2）=18、21-（2 + 1）=18、20-（2 + 0）=18。

上記の数値はすべて条件を満たしています

しかし、19-（1 + 9）=9はLより小さく、同様に18,17….1。

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

入力 − n =30 L =19

出力 −数とその桁の合計の差がL以上になるような数の数− 1

説明 − 30のみが条件を満たし、30-（3 + 0）=27> 19

入力 − n =123330 L =5466

出力 −数とその桁の合計の差がL以上になるような数の数− 6841

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

二分探索を使用して、条件を満たす最初の番号を見つけます。その数がnumの場合、条件はnum+1などにも当てはまります。

現在のmid値のいずれかが条件を満たす場合、midとendの間のすべての数値もこの条件を満たすため、カウントにend-mid+1を追加するだけで済みます。

• numとLをlong変数とします。

• 関数Digit_sum（LL num）は、数値numを取り、その桁の合計を返します。

• 最初の合計をtotal=0とします。

• whileループを使用して、リマインダーnum％10を合計に追加し、numを10減らします。num>0になるまでこれを行います。

• 合計をnumの桁の合計として返します。

• 関数Less_than_L（LL num、LL L）は、数値numと数値Lを取り、数値とその桁の合計の差がL以上になるように数値のカウントを返します

• 初期カウントを0とします。

• start=1およびend=numであるwhileループを使用してバイナリ検索を実装します。

• 中間数をtemp=（start + end）/2として計算します。

• tempとtempの桁の合計の差がL以上の場合、tempより大きいすべての数値も同じ条件を満たすことになります。

• tempを含むそのような数のカウントはnum-temp+1になります。これを追加してカウントします。そして、end=temp-1を設定します。

• それ以外の場合は、start =temp+1を設定します。

• 二分探索の最後に、カウントはそれらの間に差があり、桁の合計がL以上の数字になります

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

例

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int Digit_sum(LL num){
   LL total = 0;
   while (num > 0){
      total += num % 10;
      num = num/10;
      z}
   return total;
}
LL Less_than_L(LL num, LL L){
   LL count = 0;
   LL start = 1;
   LL end = num;
   while (start <= end){
      LL temp = (end + start) / 2;
      LL temp_2 = temp - Digit_sum(temp);
      if (temp_2 >= L){
         count = num - temp + 1;
         end = temp - 1;
      }
      else{
         start = temp + 1;
      }
   }
   return count;
}
int main(){
   LL num = 234516;
   LL L = 235;
   cout<<"Count of Numbers such that difference between the number and sum of its digits not
   less than L are: "<< Less_than_L(num, L);
   return 0;
}

出力

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

Count of Numbers such that difference between the number and sum of its digits not less than L are: 234267