Đếm tổng số chữ số từ 1 đến N trong C++

Cho số N. Đếm tổng số chữ số khi viết tất cả các số từ 1 đến N. Số 1-9: 1 chữ số; 10-99: 2 chữ số; 100-999: 3 chữ số...

Ví dụ

Đầu vào: N = 11
Đầu ra: 13 (1-9: 9 chữ số; 10,11: 4 chữ số).

Đầu vào: N = 999
Đầu ra: 2889 (9 + 180 + 2700).

Phương pháp 1: Đệ quy (Naive)

Chuyển số thành chuỗi, độ dài chuỗi = số chữ số. Gọi đệ quy cho num-1.

int total_digits(int num) {
    string str = to_string(num);
    int length = str.length();
    if (num == 1) return 1;
    return length + total_digits(num - 1);
}

Phương pháp 2: Hiệu quả (Toán học)

Duyệt i = 1, 10, 100... ≤ N. Mỗi bước cộng N - i + 1.

int total_digits(int num) {
    int count = 0;
    for (int i = 1; i <= num; i *= 10) {
        count += (num - i + 1);
    }
    return count;
}

Ví dụ hoàn chỉnh

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

int total_digits(int num) {
    int count = 0;
    for (int i = 1; i <= num; i *= 10) {
        count += (num - i + 1);
    }
    return count;
}

int main() {
    int num = 20;
    cout << "Count of total number of digits from 1 to n are: " << total_digits(num);
    return 0;
}

Kết quả

Count of total number of digits from 1 to n are: 31