Description
Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
Example 1:
Input: n = 13 Output: 6
Example 2:
Input: n = 0 Output: 0
Constraints:
0 <= n <= 109
Solutions
Solution 1: Digit DP
This problem essentially asks for the number of times the digit 1 appears in the given range [l, ..r]. The count is related to the number of digits and the value of each digit. We can use the concept of Digit DP to solve this problem. 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, ..r].
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.
The basic steps are as follows:
First, we convert the number n to a string s. Then we design a function dfs(i, cnt, 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 cnt represents the current count of the digit 1 in the number.
- 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, directly return cnt. If limit is true, up is the i-th digit of the current number. Otherwise, up = 9. Next, we iterate j from 0 to up. For each j:
- If j equals 1, we increment cnt by one.
- Recursively call dfs(i + 1, cnt, limit \land j = up).
The answer is dfs(0, 0, True).
The time complexity is O(m^2 × D), and the space complexity is O(m^2). Here, m is the length of the number n, and D = 10.
Similar Problems:
Here is the translation of the similar problems into English:
- 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
- 2376. Count Special Integers
class Solution: def countDigitOne(self, n: int) -> int: @cache def dfs(i: int, cnt: int, limit: bool) -> int: if i >= len(s): return cnt up = int(s[i]) if limit else 9 ans = 0 for j in range(up + 1): ans += dfs(i + 1, cnt + (j == 1), limit and j == up) return ans s = str(n) return dfs(0, 0, True)(code-box)
