1012.md

1012. Numbers With Repeated Digits

Solution 1

class Solution:
    def numDupDigitsAtMostN(self, n: int) -> int:
        s = str(n)
        @cache
        def f(i: int, mask: int, is_limit: bool, is_num: bool) -> int:
            if i == len(s):
                return int(is_num)
            ans = 0
            if not is_num:
                ans += f(i + 1, mask, False, False)
            low = 0 if is_num else 1
            up = int(s[i]) if is_limit else 9
            for d in range(low, up + 1):
                if (mask >> d & 1) == 0:
                    ans += f(i + 1, mask | (1 << d), is_limit and d == up, True)
            return ans
        return n - f(0, 0, True, False)