在 C++ 中查找具有给定位数和数字和的最小数字

在这个问题中，我们得到两个值：和（表示数字的和）和位数（表示数字的位数）。我们的任务是找到具有给定位数和数字和的最小数字。

让我们来看一个例子来理解这个问题：

输入

sum = 15, dgiti = 2

输出

69

解释

所有两位数且数字和为 15 的数字是：69、78、87、96。

解决方案方法

一个简单的解决方案是考虑所有位数为“位数”的数字，并找到数字和等于“和”的最小数字。

一个高效的解决方案是使用贪婪算法。我们将通过从最后一位数字（即数字的最低有效位）填充元素来创建数字。我们将考虑最低有效位的最大可能元素，然后转到下一位。

我们将尝试使最低有效位尽可能大，而最高有效位尽可能小。

程序说明了我们解决方案的工作原理：

示例

 在线演示

#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

sudhir sharma

更新于：2021年3月16日

1K+ 次浏览

开启你的职业生涯

完成课程获得认证

开始学习