Teaching Kids Programming – Dynamic Programming Algorithms to Count Numbers with Unique Digits

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10^n.

Example:
Input: 2
Output: 91
Explanation: The answer should be the total numbers in the range of 0 ≤ x < 100, excluding 11,22,33,44,55,66,77,88,99

Constraints:
0 <= n <= 8

Counting Unique Digits with Math

If there are K digits (if K is larger than 1), the first digit would be 9 choices (excluding 0), the second digit has 8 choices (including 0), the third digitis has 7 choices and so on. Thus we can sum F(K) for K is between [0 to N]. In particular and

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        if n == 0:
            return 1
        def f(k):            
            ans = 9
            for i in range(1, k):
                ans *= 10 - i
            return ans
        ans = 10
        for i in range(2, n + 1):
            ans += f(i)
        return ans

class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        if n == 0:
            return 1
        def f(k):            
            ans = 9
            for i in range(1, k):
                ans *= 10 - i
            return ans
        ans = 10
        for i in range(2, n + 1):
            ans += f(i)
        return ans

If K is more than 10, . Therefore, the time complexity for this solution could be made O(1) constant – by adding a if check.

Counting Unique Digits with Top Down Dynamic Programming

We can use Top Down Dynamic Programming Algorithm to compute the F function with That is and .

1
2
3
4
5
6
7
8
9
10

class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        @cache
        def f(n):
            if n == 0:
                return 1
            if n == 1:
                return 9
            return f(n-1)*(11-n)
        return sum(f(n) for n in range(0, n + 1))

class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        @cache
        def f(n):
            if n == 0:
                return 1
            if n == 1:
                return 9
            return f(n-1)*(11-n)
        return sum(f(n) for n in range(0, n + 1))

Remember to use @cache or @lru_cache(None), or @lru_cache(maxsize=None) to apply the memoization techique in the Top-Down Dynamic Programming Implementation!

Using Bottom Up Dynamic Programming to Count Numbers with Unique Digits

We can calculate F values with bottom-up Dynamic Programming Algorithms.

1
2
3
4
5
6
7
8

class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        dp = [0] * 11
        dp[0] = 1
        dp[1] = 9
        for i in range(2, n + 1):
            dp[i] = dp[i - 1] * (11 - i)
        return sum(dp[i] for i in range(n + 1))

class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        dp = [0] * 11
        dp[0] = 1
        dp[1] = 9
        for i in range(2, n + 1):
            dp[i] = dp[i - 1] * (11 - i)
        return sum(dp[i] for i in range(n + 1))

Here we use a array (e.g. DP) to store the Dynamic Programming intermediate values.

See also: How to Count Numbers with Unique Digits? (C/C++ Coding Exercise)

–EOF (The Ultimate Computing & Technology Blog) —