Đếm số có chữ số đầu và cuối giống nhau trong khoảng C++

Cho khoảng [first, last]. Đếm số lượng số trong khoảng có chữ số hàng đầu (first digit) và hàng đơn vị (last digit) giống nhau.

Ví dụ minh họa

Ví dụ 1:

• Input: first = 8, last = 40
• Output: 5
• Giải thích: 8, 9, 11, 22, 33.

Ví dụ 2:

• Input: first = 100, last = 200
• Output: 10
• Giải thích: 101, 111, 121, 131, 141, 151, 161, 171, 181, 191.

Mã nguồn C++ (Duyệt tuần tự)

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

int getFirstDigit(int num) {
    while (num >= 10) {
        num = num / 10;
    }
    return num;
}

int getCount(int fst, int lst) {
    int count = 0;
    for (int i = fst; i <= lst; i++) {
        int fdigit = getFirstDigit(i);
        int ldigit = i % 10;
        if (fdigit == ldigit) count++;
    }
    return count;
}

int main() {
    int first = 10, last = 23;
    cout << "So co chu so dau cuoi giong nhau: " << getCount(first, last);
    return 0;
}

Kết quả chạy chương trình

So co chu so dau cuoi giong nhau: 2

Tối ưu hóa O(1) - Công thức toán học

int countSameFirstLast(int fst, int lst) {
    if (fst > lst) return 0;
    auto countUpTo = [](int x) {
        if (x < 1) return 0;
        int count = 0;
        // Số 1 chữ số: 1-9 (9 số)
        if (x < 10) return x;
        count = 9;
        // Số 2 chữ số: 11,22,...,99 (9 số)
        if (x < 100) return count + (x - 10) / 10 + 1;
        // Số ≥3 chữ số: dạng d...d
        string s = to_string(x);
        int len = s.length();
        int firstDigit = s[0] - '0';
        
        // Các số ít chữ số hơn
        for (int l = 3; l < len; l++) {
            count += 9 * pow(10, l - 2);
        }
        // Cùng số chữ số
        count += (firstDigit - 1) * pow(10, len - 2);
        // Cùng chữ số đầu
        int mid = 0;
        for (int i = 1; i < len - 1; i++) {
            mid = mid * 10 + (s[i] - '0');
        }
        int lastDigit = s[len - 1] - '0';
        count += mid;
        if (firstDigit <= lastDigit) count++;
        return count;
    };
    return countUpTo(lst) - countUpTo(fst - 1);
}

Độ phức tạp