Leetcode 0357 Count Numbers with Unique Digits

Problem statement

https://leetcode.com/problems/count-numbers-with-unique-digits/

Solution

Simple combinations problem, let f[k] be a number of numbers with exactly k digits, then f[k] = 9 * 9 * 8 * ... * (9 - k + 2).

Complexity

Time and space complexity is O(n)$, in fact f[k] = 0 for n > 10, so it is in fact O(1).

Code

class Solution:
    def countNumbersWithUniqueDigits(self, n):
        @lru_cache(None)
        def dp(i):
            return 8*i+1 if i in [0, 1] else dp(i-1)*(11-i)
        
        return sum(dp(i) for i in range(n+1))