Đếm số có chữ số hàng đơn vị bằng k trong khoảng [first, last] C++

Cho khoảng [first, last] và chữ số k (0-9). Đếm số lượng số trong khoảng có chữ số hàng đơn vị (unit digit) bằng k.

Ví dụ minh họa

Ví dụ 1:

• Input: first = 8, last = 40, k = 8
• Output: 4
• Giải thích: 8, 18, 28, 38.

Ví dụ 2:

• Input: first = 100, last = 200, k = 9
• Output: 10
• Giải thích: 109, 119, 129, 139, 149, 159, 169, 179, 189, 199.

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

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

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

int main() {
    int first = 5, last = 30;
    int K = 5;
    cout << "So luong so co chu so hang don vi " << K << ": " << getCount(first, last, K);
    return 0;
}

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

So luong so co chu so hang don vi 5: 3

Tối ưu hóa O(1) - Toán học

Không cần duyệt, có thể tính toán trực tiếp:

int getCountOptimized(int fst, int lst, int k) {
    if (fst > lst) return 0;
    
    // Tìm số đầu tiên ≥ fst có hàng đơn vị = k
    int firstMatch = fst + ((k - fst % 10) + 10) % 10;
    if (firstMatch > lst) return 0;
    
    // Số lượng = 1 + (lst - firstMatch) / 10
    return 1 + (lst - firstMatch) / 10;
}

Độ phức tạp

Giải thích công thức

• (k - fst % 10 + 10) % 10: khoảng cách từ fst đến số tiếp theo có hàng đơn vị k.
• Các số thỏa mãn tạo thành cấp số cộng công 차가 10.