LeetCode - Count Numbers with Unique Digits (Python)
Tags: backtracking, dynamic programming, LeetCodeGiven a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.
Example:
Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99])
Hint:
- A direct way is to use the backtracking approach.
- Backtracking should contains three states which are (the current number, number of steps to get that number and a bitmask which represent which number is marked as visited so far in the current number). Start with state (0,0,0) and count all valid number till we reach number of steps equals to 10n.
- This problem can also be solved using a dynamic programming approach and some knowledge of combinatorics.
- Let f(k) = count of numbers with unique digits with length equals k.
f(1) = 10, ..., f(k) = 9 * 9 * 8 * ... (9 - k + 2)[The first factor is 9 because a number cannot start with 0].
The Backtracking Method
The following python code shows a solution using backtracking to solve the problem. It is actually an deep first search algorithm. We use a variable to record the total counts of the valid numbers. At each branch of the search tree, we increase the count if a new digit can be appended at the end of the number.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
def solve(n, num, i, res): if i == n: return for k in range(10): if i == 0 and k == 0: res[0] += 1 # the num is 0 continue if k not in num: num.append(k) res[0] += 1 # this means the current number in num is valid solve(n, num, i + 1, res) num.pop() def get_unique_digits_num(n): if n == 0: return 1 num =[] res = [0] solve(n, num, 0, res) return res[0] |
However, the backtracking method does not work when n is large.
Dynamic Programming
We can use the dynamic programming method to solve this problem. Let’s define f(k), which denotes the Count Numbers with Unique Digits when the numbers have k digits.
f[0] = 1, as there is only one number 0
f[1] = 9, the numbers are 1, 2, 3, 4, .... 9
f[2] = f[1] * 9= 9 * 9 (the numbers are 10 12 13 .... 98)
f[3] = f[2] * 8 = 9 * 9 * 8 (the numbers are 101, 102, 103, 104, ... 109, 120, 123, 124, 129 ...1... 987)
So we have: f[i] = f[i - 1] * (10 - i + 1) = 9 * 9 * 8 * ... * (10 - i + 1)
The total count of qualified numbers = f[0] + f[1] + f[2] + .... f[n]
The following python code implements this method. It can pass within 40 ms, which beats 87.8% of python submissions.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
def get(n): f = [0 for _ in range(n + 1)] sum = 0 for i in range(n + 1): if i == 0: f[i] = 1 sum += f[i] continue if i == 1: f[i] = 9 sum += f[i] continue f[i] = (10 - i + 1) * f[i - 1] sum += f[i] return sum |
