Đếm số nguyên dương có chữ số 0 và tối đa d chữ số trong C++

Cho một số d đại diện cho số chữ số. Mục tiêu là tìm số lượng các số nguyên dương có chứa chữ số 0 và có tối đa d chữ số. Tính tổng tất cả các số 1 chữ số, 2 chữ số, 3 chữ số... d chữ số chứa ít nhất một chữ số 0.

Phân tích

Đối với d = 3, để tạo một số 3 chữ số có ít nhất một 0:

• Chữ số đầu tiên (d1) có thể là 1-9: 9 cách.
• Chữ số thứ hai (d2) có thể là 0-9: 10 cách.
• Chữ số thứ ba (d3) có thể là 0-9: 10 cách.
• Tổng số 3 chữ số: 9 × 10².

Số d chữ số không có chữ số 0 nào: 9^d.
Số d chữ số có ít nhất một 0: 9 × 10^(d-1) - 9^d = 9 × (10^(d-1) - 9^(d-1)).

Ví dụ

Đầu vào: d = 4
Đầu ra: 2619
Giải thích:

Số 1 chữ số có 0: 0
Số 2 chữ số có 0: 9
Số 3 chữ số có 0: 171
Số 4 chữ số có 0: 2439
Tổng = 9 + 171 + 2439 = 2619

Đầu vào: d = 1
Đầu ra: 0 (vì 1-9 không có số nào chứa 0).

Các phương pháp

1. Phương pháp đơn giản (Naive)

Duyệt từ 1 đến d, áp dụng công thức cho từng độ dài và cộng dồn.

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

int total_count(int d) {
    int temp = 9 * (pow(10, d-1) - pow(9, d-1));
    return temp;
}

int maximum_d(int d) {
    int count = 0;
    for (int i = 1; i <= d; i++) {
        count += total_count(i);
    }
    return count;
}

int main() {
    int d = 5;
    cout << "Count of positive integers with 0 as a digit and maximum 'd' digits are: " << maximum_d(d) << endl;
    return 0;
}

Kết quả: 33570

2. Phương pháp hiệu quả (Sử dụng cấp số nhân)

Tổng hợp công thức thành dạng đóng:

count = 9 × (10^d - 1)/9 - 9 × (9^d - 1)/8 = (10^d - 1) - (9/8) × (9^d - 1)

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

int maximum_d(int d) {
    int temp_1 = 9 * ((pow(10, d) - 1) / 9);
    int temp_2 = 9 * ((pow(9, d) - 1) / 8);
    int count = temp_1 - temp_2;
    return count;
}

int main() {
    int d = 4;
    cout << "Count of positive integers with 0 as a digit and maximum 'd' digits are: " << maximum_d(d) << endl;
    return 0;
}

Kết quả: 2619