โปรแกรมนับจำนวนครั้งที่ตัวเลขปรากฏในช่วง 1 ถึง N ใน Python

ได้รับจำนวนเต็ม n และหลัก d (0-9) หา จำนวนครั้งที่หลัก d ปรากฏ ในตัวเลข 1 ถึง n

ตัวอย่าง

Input: n = 45, d = 5

Output: 5 (ใน 5, 15, 25, 35, 45)

แนวทางแก้ปัญหา

Mathematical Digit DP (Recursive Formula):

• นับหลัก d ใน 1..n โดยแบ่งเป็น:
  • ส่วนที่สมบูรณ์ (complete cycles of 10): solve(n//10 - 1) * 10 + (n//10)
  • ส่วนเศษ: วนตรวจสอบ n//10 * 10 ถึง n
• กรณีพิเศษ d == 0: ต้องลบ 1 เพราะไม่มี leading zeros

การใช้งาน (Python)

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  # ปรับ leading zero
        
        # ส่วนเศษ
        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

วิธีทางเลือก: Iterative Digit DP (เร็วกว่า)

def count_digit(n, d):
    count = 0
    factor = 1
    while factor <= n:
        lower = n % factor
        cur = (n // factor) % 10
        higher = n // (factor * 10)
        
        if cur < d:
            count += higher * factor
        elif cur == d:
            count += higher * factor + lower + 1
        else:
            count += (higher + 1) * factor
        
        if d == 0:
            count -= factor  # leading zeros
        
        factor *= 10
    return count

ความซับซ้อน

• Recursive: O(log n) recursion depth
• Iterative: O(log n) time, O(1) space