357. Count Numbers with Unique Digits
Description
Given an integer n
, return the count of all numbers with unique digits, x
, where 0 <= x < 10n
.
Example 1:
Input: n = 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
Example 2:
Input: n = 0 Output: 1
Constraints:
0 <= n <= 8
Solutions
Solution 1: State Compression + Digit DP
This problem essentially asks for the number of numbers in the given range $[l, ..r]$ that satisfy certain conditions. The conditions are related to the composition of the numbers rather than their size, so we can use the concept of Digit DP to solve it. In Digit DP, the size of the number has little impact on the complexity.
For the range $[l, ..r]$ problem, we generally convert it to the problem of $[1, ..r]$ and then subtract the result of $[1, ..l - 1]$, i.e.:
$$ ans = \sum_{i=1}^{r} ans_i - \sum_{i=1}^{l-1} ans_i $$
However, for this problem, we only need to find the value for the range $[1, ..10^n-1]$.
Here, we use memoized search to implement Digit DP. We search from the starting point downwards, and at the lowest level, we get the number of solutions. We then return the answers layer by layer upwards, and finally get the final answer from the starting point of the search.
Based on the problem information, we design a function $\textit{dfs}(i, \textit{mask}, \textit{lead})$, where:
- The digit $i$ represents the current position being searched, starting from the highest digit, i.e., $i = 0$ represents the highest digit.
- The digit $\textit{mask}$ represents the current state of the number, i.e., the $j$-th bit of $\textit{mask}$ being $1$ indicates that the digit $j$ has been used.
- The boolean $\textit{lead}$ indicates whether the current number only contains leading $0$s.
The function executes as follows:
If $i$ exceeds the length of the number $n$, i.e., $i < 0$, it means the search is over, directly return $1$.
Otherwise, we enumerate the digits $j$ from $0$ to $9$ for the position $i$. For each $j$:
- If the $j$-th bit of $\textit{mask}$ is $1$, it means the digit $j$ has been used, so we skip it.
- If $\textit{lead}$ is true and $j = 0$, it means the current number only contains leading $0$s. When we recurse to the next level, $\textit{lead}$ remains true.
- Otherwise, we recurse to the next level, update the $j$-th bit of $\textit{mask}$ to $1$, and set $\textit{lead}$ to false.
Finally, we sum all the results from the recursive calls to the next level, which is the answer.
The answer is $\textit{dfs}(n - 1, 0, \textit{True})$.
The time complexity is $O(n \times 2^D \times D)$, and the space complexity is $O(n \times 2^D)$. Here, $n$ is the length of the number $n$, and $D = 10$.
Similar Problems:
- 233. Number of Digit One
- 600. Non-negative Integers without Consecutive Ones
- 788. Rotated Digits
- 902. Numbers At Most N Given Digit Set
- 1012. Numbers with Repeated Digits
- 2376. Count Special Integers
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
|