C++で指定された桁数と桁数の合計で最大の数値を検索します

この問題では、2つの整数値が与えられます。Nは数値の桁数を示し、sumは数値の桁の合計を示します。私たちのタスクは、指定された桁数と桁数の合計で最大の数を見つけることです 。

問題を理解するために例を見てみましょう

Input : N = 3, sum = 15
Output : 960

ソリューションアプローチ

この問題を解決する簡単な方法は、N桁の数字すべてを最大から最小までトラバースすることです。合計が数値を返すのと等しい場合は、数字の合計数を見つけます。

例

ソリューションの動作を説明するプログラム

#include <iostream>
using namespace std;
int digitSum(int n){
   int sum = 0; 
   while(n){
      sum += n%10; 
      n = n/10;
   }
   return sum;
}
int findLargestNumWithSum(int N, int sum){
   if (sum == 0){
      if(N == 1)
         return -1;
      else
         return -1;
   }
   if (sum > 9*N){
      return -1;
   }
   int num = 1;
   for(int i = 0; i < N; i++) 
      num *= 10;
   while(1){
      if(digitSum(num) == sum){
         return num;
      }
      num -- ;
      if(num == 0)
         return -1;
   }
}
int main(){
   int sum = 25, N = 3;
   cout<<"The largest "<<N<<" digit number with sum "<<sum<<" is "<< findLargestNumWithSum(N, sum);
   return 0;
}

出力

The largest 3 digit number with sum 25 is 997

この問題を解決する別のアプローチは、欲張りアプローチを使用することです。これを行うには、MSBから開始し、合計から可能な限り高い数値を配置し、合計から減算します。

このステップをN回実行し、必要な数を取得します。したがって、合計が9より大きい場合は、現在の桁に9を配置し、9未満の場合は、合計を現在の桁に配置します。 MSBからLSBまでのすべての数字に対して、このプロセスを実行します。

例

ソリューションの動作を説明するプログラム

#include <iostream>
using namespace std;
int findLargestNumWithSum(int N, int sum){
   if (sum == 0){
      if(N == 1)
         return -1;
      else
         return -1;
   }
   if (sum > 9*N){
      return -1;
   }
   int num = 0;
   for (int i = 0; i < N; i++){
      if (sum >= 9){
         num += 9;
         sum -= 9;
         if(i < (N - 1)){
            num *= 10;
         }
      }
      else{
         num += sum;
         sum = 0;
         if( i < (N - 1)) 
             num *= 10;
      }
   }
   return num;
}
int main(){
   int sum = 25,
   N = 3;
   cout<<"The largest "<<N<<" digit number with sum "<<sum<<" is "<<findLargestNumWithSum(N, sum);
   return 0;
}

出力

The largest 3 digit number with sum 25 is 997