Đếm số (nhỏ hơn hoặc bằng N) có tổng chữ số cho trước trong C++

Cho một chuỗi str chứa một số và một tổng total đầu vào. Mục tiêu: tìm các số đến str có tổng chữ số bằng total.

Hiểu qua ví dụ

Đầu vào: N = "110", sum = 5

Đầu ra: Số lượng số ≤ N có tổng chữ số = 5: 7

Giải thích: Các số ≤ 110 có tổng chữ số 5: 5, 14, 23, 32, 41, 50, 104.

Đầu vào: N = "1000", sum = 3

Đầu ra: Số lượng số ≤ N có tổng chữ số = 3: 10

Giải thích: Các số: 3, 12, 21, 30, 102, 111, 120, 201, 210, 300.

Phương pháp sử dụng

Sử dụng quy hoạch động lưu tổng số và chữ số trong mảng arr[18][2][162]. 18 cho số 18 chữ số tối đa, 2 cho giá trị 0/1, 162 cho tổng tối đa (18*9=162).

Giá trị arr[i][j][k] = số lượng số có i chữ số đầu tiên được xem xét, j = 0/1 tùy số hiện tại nhỏ hơn hay bằng i chữ số đầu của N. k = tổng i chữ số.

Nếu i = số chữ số của N và k = tổng đầu vào kết quả = 1 ngược lại 0.

Điền chữ số tiếp theo (i+1): nếu j = 1 thì chữ số tiếp theo chỉ 0 đến chữ số i+1 của N. Nếu j = 0 có thể đặt 0-9.

• Nhập chuỗi str đại diện số N và total.
• Mảng arr[18][2][162] khởi tạo -1 bằng memset.
• Hàm count_digits(int i, bool check, int temp, int total, string str, int size) đệ quy điền mảng và trả về đếm.
• Nếu i == size và temp == total trả về 1 else 0.
• Nếu arr[i][check][temp] != -1 trả về giá trị.
• Duyệt chữ số '0'-'9': nếu check = 0 và str[i] break.
• check_2 = check || ch < str[i], temp_2 = temp + (ch - '0').
• Đệ quy count_digits(i+1, check_2, temp_2, total, str, size) cộng vào count.
• Trả về count.

Ví dụ mã nguồn

#include <bits/stdc++.h> 
using namespace std; 

int arr[18][2][162]; 

int count_digits(int i, bool check, int temp, int total, string str, int size) { 
    if (i == size) { 
        if (temp == total) return 1; 
        else return 0; 
    } 
    int count = arr[i][check][temp]; 
    if (count != -1) return count; 
    count = 0; 
    bool check_2; 
    int temp_2; 
    for (char ch = '0'; ch <= '9'; ch++) { 
        if (!check) { 
            if (ch > str[i]) break; 
        } 
        check_2 = check || ch < str[i]; 
        temp_2 = temp + (ch - '0'); 
        count += count_digits(i + 1, check_2, temp_2, total, str, size); 
    } 
    return count; 
} 

int main() { 
    string str = "1101"; 
    int size = str.size(); 
    int total = 5; 
    memset(arr, -1, sizeof(arr)); 
    cout << "Count of numbers smaller than or equal to N with given digit sum are: " << count_digits(0, 0, 0, total, str, size); 
    return 0; 
}

Chạy mã trên cho kết quả:

Kết quả

Count of numbers smaller than or equal to N with given digit sum are: 26