数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 C++ 中查找具有给定位数和数字和的最大数
在这个问题中，我们得到了两个整数值，N 表示数字的位数，sum 表示数字的数字和。我们的任务是 *查找具有给定位数和数字和的最大数*。
让我们举一个例子来理解这个问题，
Input : N = 3, sum = 15 Output : 960
解决方案方法
解决该问题的一种简单方法是从最大到最小遍历所有 N 位数字。查找数字和数字，如果它等于 sum，则返回该数字。
示例
程序说明我们解决方案的工作原理
#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 开始，从 sum 中放置尽可能大的数字，并从 sum 中减去它。
我们将执行此步骤 N 次，我们将得到所需的数字。因此，如果 sum 大于 9，则将 9 放置到当前数字，如果它小于 9，则将 sum 放置到当前数字。执行此过程，从 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
更新于： 2022-01-28
1K+ 浏览量
广告