Tìm số nhỏ nhất với số chữ số và tổng chữ số cho trước trong C++

Trong bài toán này, cho hai giá trị: sum (tổng chữ số) và digit (số chữ số). Nhiệm vụ là tìm số nhỏ nhất có số chữ số và tổng chữ số cho trước.

Ví dụ minh họa:

Đầu vào

sum = 15, digit = 2

Đầu ra

69

Giải thích

Các số 2 chữ số có tổng 15: 69, 78, 87, 96.

Phương pháp giải

Cách đơn giản: xét tất cả số có digit chữ số, tìm số nhỏ nhất tổng chữ số = sum.

Cách hiệu quả: dùng tham lam (greedy). Tạo số bằng cách điền từ chữ số cuối (LSB). Chọn chữ số lớn nhất có thể cho LSB, rồi đến vị trí tiếp theo. Giữ LSB lớn nhất, MSB nhỏ nhất.

Chương trình minh họa:

Ví dụ

#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; 
}

Kết quả

Smallest number is 159