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 dfs(i, mask, 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 mask represents the current state of the number, i.e., the j-th bit of mask being 1 indicates that the digit j has been used.
- The boolean lead indicates whether the current number only contains leading 0s.
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 mask is 1, it means the digit j has been used, so we skip it.
- If lead is true and j = 0, it means the current number only contains leading 0s. When we recurse to the next level, lead remains true.
- Otherwise, we recurse to the next level, update the j-th bit of mask to 1, and set lead to false.
Finally, we sum all the results from the recursive calls to the next level, which is the answer.
The answer is dfs(n - 1, 0, True).
The time complexity is O(n × 2^D × D), and the space complexity is O(n × 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
class Solution: def countNumbersWithUniqueDigits(self, n: int) -> int: @cache def dfs(i: int, mask: int, lead: bool) -> int: if i < 0: return 1 ans = 0 for j in range(10): if mask >> j & 1: continue if lead and j == 0: ans += dfs(i - 1, mask, True) else: ans += dfs(i - 1, mask | 1 << j, False) return ans return dfs(n - 1, 0, True)(code-box)
