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 <= 109Problem Overview: Given an integer n, count how many times the digit 1 appears in all non‑negative integers from 0 to n. Instead of generating every number, the challenge is recognizing patterns in how digits repeat across positions.
Approach 1: Brute Force Enumeration (Time: O(n log n), Space: O(1))
The straightforward idea is to iterate through every integer from 1 to n, convert each number into digits, and count how many times the digit 1 appears. You can extract digits using modulo and division (num % 10, num /= 10) or convert the number to a string and scan it. The complexity grows quickly because every number may contain up to log10(n) digits, making the total work roughly O(n log n). This approach works for small values of n but becomes far too slow when n reaches millions or billions.
Approach 2: Counting by Digit Position (Time: O(log n), Space: O(1))
The optimal solution analyzes each digit position independently. For every position (ones, tens, hundreds, etc.), calculate how many full cycles of numbers contribute a 1 at that position. For a given position value factor = 1, 10, 100..., split the number into three parts: higher digits to the left, the current digit, and lower digits to the right. The count contributed by that position depends on the current digit:
If the current digit is 0, the number of ones comes entirely from completed cycles (higher * factor). If the current digit is 1, add the remaining numbers in the partial cycle (higher * factor + lower + 1). If the current digit is greater than 1, a full additional cycle contributes ((higher + 1) * factor). Iterating through digit positions requires only log10(n) steps, which reduces the time complexity to O(log n). This method relies on simple arithmetic and pattern observation rather than explicit enumeration, making it highly efficient for large inputs.
The technique is a classic example of digit decomposition used in math problems involving ranges of numbers. The reasoning process resembles state transitions seen in dynamic programming problems and can also be implemented recursively using recursion to process digit ranges.
Recommended for interviews: Interviewers expect the digit-position counting approach. Starting with the brute force method shows you understand the problem definition, but quickly moving to the mathematical pattern demonstrates algorithmic maturity. The O(log n) solution is the standard optimal answer and scales easily to very large values of n.
In this approach, we iterate through each number from 0 to n. For each number, we count the number of times digit 1 appears. Although this approach is simple, it's not optimal for large values of n due to its high time complexity.
The code iterates from 1 to n and for each number, it counts the number of the digit 1 by repeatedly dividing the number by 10 and checking the remainder. It increments count each time a 1 is found.
Time Complexity: O(n * log10(n)), as it checks each digit of each number from 1 to n.
Space Complexity: O(1), as it uses a fixed amount of space.
This optimized approach examines digit positions and calculates how many times 1 appears at each position up to n. It leverages the structure of numbers and is more efficient for large values of n.
The C code iterates over each digit position and calculates how often a 1 would appear at that position using arithmetic based on the surrounding digits. The core idea is to count 1s in each digit position separately.
Time Complexity: O(log10(n)), as it iterates digit by digit.
Space Complexity: O(1), as it uses a fixed amount of space.
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:
represents the current position being searched, starting from the highest digit, i.e., i = 0 represents the highest digit. represents the current count of the digit 1 in the number. 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:
equals 1, we increment cnt by one..The answer is dfs(0, 0, True).
The time complexity is O(m^2 times 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:
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n * log10(n)), as it checks each digit of each number from 1 to n. |
| Counting by Digit Position | Time Complexity: O(log10(n)), as it iterates digit by digit. |
| Digit DP | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n log n) | O(1) | Useful for understanding the problem or when n is very small. |
| Counting by Digit Position | O(log n) | O(1) | Optimal solution for large inputs and the expected approach in coding interviews. |
Leetcode 233(Hard) Number of Digit One: Simple C++ Solution • Shivam Patel • 11,179 views views
Watch 9 more video solutions →Practice Number of Digit One with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor