2025-08-21 09:07:22 +0000 UTC

class Solution:
    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:
        low, hgh = str(low), str(high)  
        n = len(hgh)                    
        low = low.rjust(n,'0')          
        @lru_cache(None)
        def dfs(idx,
                belowHgh,                
                aboveLow,                
                init0,
                parity,
                rem):                    
            if idx == n: 
                return rem == 0 == parity  
            lowD, hghD = int(low[idx]), int(hgh[idx])
            res = 0
            for digit in range(0 if aboveLow else lowD,
                               (9 if belowHgh else hghD) + 1):
                res += dfs(idx + 1,
                           belowHgh or digit < hghD,
                           aboveLow or digit > lowD,
                           init0 and not digit,
                           parity + digit % 2 - (
                                    not init0 and not digit or
                                    digit and not digit % 2),
                           (rem * 10 + digit) % k)
            return res
        return dfs(0, False, False, True, 0, 0)