C++ Tìm số trong khoảng có gốc số cho trước

Gốc số (digital root) của số là tổng các chữ số lặp lại cho đến khi còn 1 chữ số. Cho khoảng [l, r] và X (1 chữ số), đếm số trong khoảng có gốc số = X. Ví dụ:

Input: l=13, r=25, X=4 → Output: 2 (số 13 và 22)
Input: l=11, r=57, X=? → Output: 6

Phương pháp giải

Đơn giản

Duyệt l đến r, tính gốc số từng số. O(N).

Hiệu quả

Gốc số của n = n%9 (nếu chia hết 9 thì gốc số = 9, ta đổi X=9 thành 0). Chia khoảng thành nhóm 9 số. Mỗi nhóm có đúng 1 số %9 = X. Đếm số nhóm đầy đủ + kiểm tra số dư.

Ví dụ minh họa

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

int main() {
    int l = 13, r = 25, X = 4;
    if (X == 9) X = 0;

    int total = r - l + 1;
    int groups = total / 9;
    int result = groups;
    int left_out = total % 9;

    for (int i=r; i>r-left_out; i--)
        if (i % 9 == X) result++;

    cout << "Số lượng: " << result;
    return 0;
}

Kết quả

Số lượng: 2

Kết luận

Đếm số có gốc số X trong [l,r] bằng chia nhóm 9: O(1) thay vì O(N). Code C++ áp dụng cho C, Java, Python. Hy vọng hữu ích.