Đếm chữ số 1 (Number of Digit One) trong C++

Cho số n, đếm tổng số chữ số 1 xuất hiện trong tất cả số từ 1 đến n.

Ví dụ

n = 15: Các số có chữ số 1: 1, 10, 11, 12, 13, 14, 15.

Số lượng chữ số 1: 1 + 1 + 2 + 1 + 1 + 1 + 1 = 8.

Thuật toán toán học (O(log n))

Xét từng vị trí chữ số (hàng đơn vị, chục, trăm...). Với vị trí có trọng số i (1, 10, 100...):

• a = n / i (phần trước vị trí hiện tại)
• b = n % i (phần sau vị trí hiện tại)
• x = a % 10 (chữ số tại vị trí hiện tại)

Số lần chữ số 1 xuất hiện tại vị trí này:

• x == 0: (a/10) * i
• x == 1: (a/10) * i + (b + 1)
• x > 1: (a/10 + 1) * i

Cài đặt C++

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

class Solution {
public:
    int countDigitOne(int n) {
        int ret = 0;
        for (long long i = 1; i <= n; i *= 10) {
            int a = n / i;
            int b = n % i;
            int x = a % 10;
            if (x == 1) ret += (a / 10) * i + (b + 1);
            else if (x == 0) ret += (a / 10) * i;
            else ret += (a / 10 + 1) * i;
        }
        return ret;
    }
};

int main() {
    Solution ob;
    cout << ob.countDigitOne(15);
    return 0;
}

Độ phức tạp

• Thời gian: O(log n) — số chữ số của n.
• Không gian: O(1).

Input / Output

Input:  15
Output: 8