ในปัญหานี้ เราได้รับค่าสองค่า คือ ผลรวม (แทนผลรวมของหลัก) และ digit (แทนจำนวนหลัก) งานของเราคือหาตัวเลขที่น้อยที่สุดที่มีจำนวนหลักและผลรวมหลักที่กำหนด
มาดูตัวอย่างเพื่อเข้าใจปัญหา
Input
sum = 15, digit = 2
Output
69
อธิบาย
ตัวเลข 2 หลักที่มีผลรวม 15 ได้แก่: 69, 78, 87, 96
วิธีแก้ปัญหา
วิธีแก้ที่ง่ายคือพิจารณาตัวเลขทั้งหมดที่มีจำนวนหลักเท่ากับ digit และหาตัวเลขที่น้อยที่สุดที่ผลรวมหลักเท่ากับ sum
วิธีที่มีประสิทธิภาพมากกว่าคือใช้ greedy approach เราจะสร้างตัวเลขโดยเติมจากหลักสุดท้าย (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
