LeetCode – Count Numbers with Unique Digits (Python)

Tags: , ,

Given 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:

  1. A direct way is to use the backtracking approach.
  2. 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.
  3. This problem can also be solved using a dynamic programming approach and some knowledge of combinatorics.
  4. Let f(k) = count of numbers with unique digits with length equals k.
  5. 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.  

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.