Chương trình đếm số lần xuất hiện chữ số trong khoảng 1 đến n trong Python

Cho số nguyên dương n và chữ số d (0-9). Đếm số lần d xuất hiện trong các số từ 1 đến n.

Ví dụ: n=45, d=5 → 5 (các số: 5, 15, 25, 35, 45).

Giải thuật (Đệ quy chia theo hàng chục + Xử lý phần dư)

Hàm solve(n, d):

• Nếu n < 0: 0.
• k = n//10 - 1. Gọi đệ quy solve(k, d): mỗi chu kỳ 10 số có solve(k,d)*10 + k+1 lần xuất hiện (trừ trường hợp d=0 trừ 1 do số 0 không tính).
• Xử lý phần dư từ m = (n//10)*10 đến n bằng chuyển string đếm.

Ví dụ minh họa

class Solution:
    def solve(self, n, d):
        if n < 0:
            return 0
        k = n // 10 - 1
        ans = self.solve(k, d) * 10 + k + 1
        if d == 0:
            ans -= 1
        m = (n // 10) * 10
        while m <= n:
            ans += str(m).count(str(d))
            m += 1
        return ans

ob = Solution()
print(ob.solve(45, 5))  # Output: 5

Đầu vào / Đầu ra

Input: 45, 5

Output: 5