ในปัญหานี้ เราได้รับค่าจำนวนเต็มสองค่า N แสดงถึงการนับหลักของตัวเลขและผลรวมที่แสดงถึงผลรวมของตัวเลข งานของเราคือ หาจำนวนที่มากที่สุดด้วยจำนวนหลักที่กำหนดและผลรวมของหลัก .
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
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
อีกวิธีในการแก้ปัญหาคือการใช้ Greedy Approach เราจะทำสิ่งนี้โดยเริ่มจาก 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
