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

Cho N (số chữ số) và sum (tổng chữ số). Nhiệm vụ: tìm số lớn nhất có N chữ số và tổng chữ số = sum.

Ví dụ minh họa

Input: N = 3, sum = 15 Output: 960

Phương pháp 1: Duyệt ngược từ số lớn nhất

Tính tổng chữ số, duyệt giảm dần từ số N chữ số lớn nhất.

Phương pháp 2: Tham lam (Greedy) - Tối ưu O(N)

Từ chữ số hàng chục ngàn (MSB), đặt chữ số lớn nhất có thể (9 nếu sum >= 9, ngược lại đặt sum). Lặp N lần.

Ví dụ chương trình (Greedy)

#include <iostream> 
using namespace std; 

int findLargestNumWithSum(int N, int sum){
    if (sum == 0) return (N == 1) ? 0 : -1;
    if (sum > 9 * N) return -1;
    int num = 0;
    for (int i = 0; i < N; i++){
        if (sum >= 9) { num = num * 10 + 9; sum -= 9; }
        else { num = num * 10 + sum; sum = 0; }
    }
    return num;
}

int main(){
    int sum = 25, N = 3;
    cout << "Số " << N << " chữ số lớn nhất có tổng " << sum << " là " << findLargestNumWithSum(N, sum);
    return 0;
}

Kết quả

Số 3 chữ số lớn nhất có tổng 25 là 997