Description
Given an integer n, return the number of positive integers in the range [1, n] that have at least one repeated digit.
Example 1:
Input: n = 20 Output: 1 Explanation: The only positive number (<= 20) with at least 1 repeated digit is 11.
Example 2:
Input: n = 100 Output: 10 Explanation: The positive numbers (<= 100) with atleast 1 repeated digit are 11, 22, 33, 44, 55, 66, 77, 88, 99, and 100.
Example 3:
Input: n = 1000 Output: 262
Constraints:
1 <= n <= 109
Solutions
Solution 1: State Compression + Digit DP
The problem requires counting the number of integers in the range [1, .., n] that have at least one repeated digit. We can approach this by defining a function f(n) that counts the number of integers in the range [1, .., n] with no repeated digits. Then, the answer is n - f(n).
Additionally, we can use a binary number to record the digits that have appeared in the number. For example, if the digits 1, 2, and 4 have appeared, the corresponding binary number is \underline{1}0\underline{1}\underline{1}0.
Next, we use memoization to implement digit DP. We start searching from the top, get the number of solutions at the bottom, and return the answers layer by layer until we get the final answer from the starting point.
The basic steps are as follows:
We convert the number n into a string s. Next, we design a function dfs(i, mask, lead, limit), where:
- The integer i represents the current digit index, starting from 0.
- The integer mask represents the digits that have appeared so far, using a binary number. The j-th bit of mask being 1 indicates that digit j has appeared, while 0 indicates it has not.
- The boolean lead indicates whether the current number contains only leading zeros.
- The boolean limit indicates whether the current position is restricted by the upper bound.
The function executes as follows:
If i is greater than or equal to m, it means we have processed all digits. If lead is true, it means the current number is a leading zero, and we should return 0. Otherwise, we should return 1.
Otherwise, we calculate the upper bound up. If limit is true, then up is the digit corresponding to s[i]. Otherwise, up is 9.
Then, we enumerate the current digit j in the range [0, up]. If j is 0 and lead is true, we recursively calculate dfs(i + 1, mask, true, limit \wedge j = up). Otherwise, if the j-th bit of mask is 0, we recursively calculate dfs(i + 1, mask ,|, 2j, false, limit \wedge j = up). We accumulate all the results as the answer.
The answer is n - dfs(0, 0, true, true).
The time complexity is O(log n × 2D × D), and the space complexity is O(log n × 2D). Here, 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
- 2376. Count Special Integers
class Solution: def numDupDigitsAtMostN(self, n: int) -> int: @cache def dfs(i: int, mask: int, lead: bool, limit: bool) -> int: if i >= len(s): return lead ^ 1 up = int(s[i]) if limit else 9 ans = 0 for j in range(up + 1): if lead and j == 0: ans += dfs(i + 1, mask, True, False) elif mask >> j & 1 ^ 1: ans += dfs(i + 1, mask | 1 << j, False, limit and j == up) return ans s = str(n) return n - dfs(0, 0, True, True)(code-box)
