Python O(1) time
The idea is to first count the numbers that have distinct digits. There are two cases. (1) Without the limitation of being at most n, there are 9*9*8*...(9-k+2)
The idea is to first count the numbers that have distinct digits. There are two cases. (1) Without the limitation of being at most `n`, there are `9*9*8*...(9-k+2)` such numbers with `k` digits. (2) With the limitation `n`, we can count such numbers in ranges. For example, for `n = 3579`, we count the numbers with distinct digits as follows:\n[1, 10): 1 digit without limitation\n[10, 100): 2 digits without limitation\n[100, 1000): 3 digits without limitation\n[1000, 3000): 4 digits of the form {1,2}???\n[3000, 3500): 4 digits of the form 3{0,1,2,4}??\n[3500, 3570): 4 digits of the form 35{0,1,2,4,6}?\n[3570, 3579): 4 digits of the form 357{0,1,2,3,4,6,8}\n{3579}: 4 digits of the form 3579\n\nSince the complexity is linear in the number of digits of `n`, it is O(1).\n\n```\nclass Solution:\n    def numDupDigitsAtMostN(self, n: int) -> int:\n        \n        print = lambda *args: None\n        \n        n2 = min(n, 10**10-1)\n        m = len(str(n2))\n        print(f\'up to {n2} ({m} digits)\')\n        \n        @lru_cache\n        def num_perms(start:int, count:int) -> int:\n            if count <= 0:\n                return 1\n            elif count == 1:\n                return start\n            return start * num_perms(start-1, count-1)\n        \n        no_repeats = 0\n        for k in range(1, m):\n            no_repeats += 9 * num_perms(9, k-1)\n        print(f\'up to length {m-1} no repeat: {no_repeats}\')\n            \n        digits = []\n        n3 = n2\n        while n3 > 0:\n            digits.append(n3 % 10)\n            n3 //= 10\n        digits = digits[::-1]\n        nd = len(digits)\n        print(digits, nd)\n        fixed_digits = set()\n        for i, d in enumerate(digits):\n            below = range(1,d) if i==0 else range(d)\n            cand = set(below) - fixed_digits\n            nc = len(cand)\n            if i == 0:\n                no_repeats_i = nc * num_perms(9, nd-i-1)\n            else:\n                no_repeats_i = nc * num_perms(10-i-1, nd-i-1)\n            print(f\'no repeats fixing {digits[:i]}: {no_repeats_i}, cand={cand}\')\n            no_repeats += no_repeats_i\n            \n            if d in fixed_digits:\n                break\n            fixed_digits.add(d)\n        if len(fixed_digits) == nd:\n            no_repeats += 1\n        print(f\'total no repeat: {no_repeats}\')\n        return n - no_repeats\n```
[]