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

この問題では、sum（桁の合計を表す）とdigit（桁数を表す）の2つの値が与えられます。私たちの仕事は、与えられた桁数と桁数の合計で最小の数を見つけることです。

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

入力

sum = 15, dgiti = 2

出力

69

説明

合計が15の2桁の数字はすべて、69、78、87、96です。

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

この問題の簡単な解決策は、digitcountを持つすべての数値を桁と見なし、桁の合計が合計に等しい最小の数値を見つけることです。

効率的な解決策は、貪欲なアプローチを使用することです。最後の桁、つまり数値のLSBから要素を入力して数値を作成します。LSBの可能な最大の要素を検討してから、次の位置に移動します。

LSBをできるだけ大きくし、MSBをできるだけ小さくするようにします。

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

例

#include <iostream>
using namespace std;
void findSmallestNumWithSum(int digit, int sum) {
   if (sum == 0) {
      if(digit == 1)
         cout<<"Smallest number is 0";
      else
         cout<<"Smallest number with sum cannot be found";
      return ;
   }
   if (sum > 9*digit) {
      cout<<"Smallest number with sum cannot be found";
      return ;
   }
   int number[digit];
   sum -= 1;
   for (int i = digit-1; i>0; i--) {
      if (sum > 9) {
         number[i] = 9;
         sum -= 9;
      } else {
         number[i] = sum;
         sum = 0;
      }
   }
   number[0] = sum + 1;
   cout<<"Smallest number is ";
   for (int i=0; i<digit; i++)
      cout<<number[i];
}
int main() {
   int sum = 15, digit = 3;
   findSmallestNumWithSum(digit, sum);
   return 0;
}

出力

Smallest number is 159