2376. Count Special Integers
Description
We call a positive integer special if all of its digits are distinct.
Given a positive integer n
, return the number of special integers that belong to the interval [1, n]
.
Example 1:
Input: n = 20 Output: 19 Explanation: All the integers from 1 to 20, except 11, are special. Thus, there are 19 special integers.
Example 2:
Input: n = 5 Output: 5 Explanation: All the integers from 1 to 5 are special.
Example 3:
Input: n = 135 Output: 110 Explanation: There are 110 integers from 1 to 135 that are special. Some of the integers that are not special are: 22, 114, and 131.
Constraints:
1 <= n <= 2 * 109
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, ..n]$.
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}, \textit{limit})$, 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 boolean $\textit{limit}$ indicates whether the current number is restricted by the upper bound.
The function executes as follows:
If $i$ exceeds the length of the number $n$, it means the search is over. If $\textit{lead}$ is true, it means the current number only contains leading $0$s, so return $0$. Otherwise, return $1$.
If $\textit{limit}$ is false and $\textit{lead}$ is false and the state of $\textit{mask}$ has been memoized, directly return the memoized result.
Otherwise, we calculate the current upper bound $up$. If $\textit{limit}$ is true, $up$ is the $i$-th digit of the current number. Otherwise, $up = 9$.
Then we iterate over $[0, up]$. For each digit $j$, if the $j$-th bit of $\textit{mask}$ is $1$, it means the digit $j$ has been used, so we skip it. Otherwise, if $\textit{lead}$ is true and $j = 0$, it means the current number only contains leading $0$s, so we recursively search the next digit. Otherwise, we recursively search the next digit and update the state of $\textit{mask}$.
Finally, if $\textit{limit}$ is false and $\textit{lead}$ is false, memoize the current state.
Return the final answer.
The time complexity is $O(m \times 2^D \times D)$, and the space complexity is $O(m \times 2^D)$. Here, $m$ is the length of the number $n$, and $D = 10$.
Similar Problems:
- 233. Number of Digit One
- 357. Count Numbers with Unique Digits
- 600. Non-negative Integers without Consecutive Ones
- 788. Rotated Digits
- 902. Numbers At Most N Given Digit Set
- 1012. Numbers with Repeated Digits
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
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 33 34 35 |
|
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 33 34 |
|