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.:
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 dfs(i, mask, lead, 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 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 boolean 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 lead is true, it means the current number only contains leading 0s, so return 0. Otherwise, return 1.
If limit is false and lead is false and the state of mask has been memoized, directly return the memoized result.
Otherwise, we calculate the current upper bound up. If 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 mask is 1, it means the digit j has been used, so we skip it. Otherwise, if lead is true and j = 0, it means the current number only contains leading 0s, so we recursively search the next digit. Otherwise, we recursively search the next digit and update the state of mask.
Finally, if limit is false and lead is false, memoize the current state.
Return the final answer.
The time complexity is O(m × 2D × D), and the space complexity is O(m × 2D). 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
class Solution: def countSpecialNumbers(self, n: int) -> int: @cache def dfs(i: int, mask: int, lead: bool, limit: bool) -> int: if i >= len(s): return int(lead ^ 1) up = int(s[i]) if limit else 9 ans = 0 for j in range(up + 1): if mask >> j & 1: continue if lead and j == 0: ans += dfs(i + 1, mask, True, limit and j == up) else: ans += dfs(i + 1, mask | 1 << j, False, limit and j == up) return ans s = str(n) return dfs(0, 0, True, True)(code-box)
