Number of Digit One
Last Updated: March 28, 2026
Understanding the Problem
We are not just counting which numbers contain a 1. We are counting every individual occurrence of the digit 1 across all numbers from 0 to n. So the number 11 contributes 2, the number 111 contributes 3, and so on.
A brute force approach would iterate through every number from 1 to n and count the 1s in each. But with n up to 10^9, that means potentially iterating through a billion numbers and examining each digit. That is way too slow.
The key insight is that we can analyze each digit position independently. Instead of asking "how many 1s are in number k?", we flip the question: "how many times does digit 1 appear in the ones place across all numbers from 0 to n? In the tens place? In the hundreds place?" This position-by-position counting leads to an O(log n) solution.
Key Constraints:
0 <= n <= 10^9→ With n up to a billion, we absolutely cannot iterate through all numbers. Even O(n) is borderline at 10^9 operations. We need O(log n) or O(1).ncan be 0 → Edge case where the answer is simply 0.
Approach 1: Brute Force
Intuition
The most straightforward idea: iterate through every number from 1 to n, convert each to its digits, and count how many of those digits are 1. Add them all up.
This is dead simple to implement. For each number, we repeatedly extract digits using modulo and division, checking if each digit equals 1. The approach is correct but far too slow for the given constraints.
Algorithm
- Initialize
count = 0. - For each number
ifrom 1 ton:
a. While i > 0, check if i % 10 == 1. If so, increment count.
b. Divide i by 10 to move to the next digit.
- Return
count.
Example Walkthrough
Code
- Time Complexity: O(n log n). We iterate through n numbers, and for each number we examine up to log10(n) digits.
- Space Complexity: O(1). We only use a counter and a temporary variable. No extra data structures.
With n up to 10^9, this brute force is way too slow. The digit 1 appears in predictable patterns at each position. What if we could calculate the count at each position directly using just the digits of n?
Approach 2: Digit-by-Digit Mathematical Counting (Optimal)
Intuition
Instead of scanning every number, we analyze each digit position independently and calculate how many times the digit 1 occupies that position across all numbers from 0 to n.
We decompose n relative to each digit position into three parts: the higher part (digits to the left), the current digit, and the lower part (digits to the right). The place value is the factor (1, 10, 100, ...).
The tens digit cycles through 0-9 repeatedly. For each full cycle controlled by the higher part, the digit 1 appears exactly factor times. This gives us three cases:
- Current digit = 0: Only complete cycles contribute. Count = higher * factor.
- Current digit = 1: Complete cycles plus a partial cycle. Count = higher * factor + lower + 1.
- Current digit >= 2: Complete cycles plus one full extra cycle. Count = (higher + 1) * factor.
We repeat this for every digit position and sum up.
Digits at each position follow a repeating pattern. In the ones place, the digit 1 appears once in every group of 10 consecutive numbers (1, 11, 21, ...). In the tens place, digit 1 appears 10 times in every group of 100 (10-19, 110-119, ...). The "complete cycles" correspond to the higher digits determining how many full groups fit, and the "partial cycle" handles the remainder at the boundary.
The three cases arise naturally: if the current digit is 0, the current position never reaches 1 in the final partial group. If it is exactly 1, we are partway through the group where 1 appears. If it is 2 or more, the entire group where 1 appears is fully included.
Algorithm
- Initialize
count = 0andfactor = 1(starting from the ones place). - While
factor <= n:
a. Compute higher = n / (factor * 10) (digits to the left).
b. Compute current = (n / factor) % 10 (the digit at this position).
c. Compute lower = n % factor (digits to the right).
d. If current == 0: add higher * factor to count.
e. If current == 1: add higher * factor + lower + 1 to count.
f. If current >= 2: add (higher + 1) * factor to count.
g. Multiply factor by 10 to move to the next position.
- Return
count.
Example Walkthrough
Code
- Time Complexity: O(log n). We iterate once for each digit position. A number with value n has log10(n) + 1 digits, so the loop runs at most 10 times for n up to 10^9.
- Space Complexity: O(1). We only use a fixed number of variables regardless of input size.
The mathematical approach is already optimal at O(log n). But what if the problem asked us to count numbers with exactly k ones, or apply more complex constraints on the digits? A more generalizable framework exists.
Approach 3: Recursive Digit DP
Intuition
There is another way to think about this problem that generalizes well to counting any digit (not just 1) and to variations like "count numbers with at most k ones." The idea is digit dynamic programming, where we process the number from the most significant digit to the least, tracking whether we are still "tight" (constrained by n) or "free" (already placed a smaller digit earlier, so all remaining digits can be 0-9).
At each position, we try placing digits 0 through 9 (or 0 through the corresponding digit of n if we are still tight). When we place a 1, we need to count how many numbers will include this particular 1. If we are free (not tight), that is 10^(remaining positions). If we are still tight and this is the last position, it is just 1.
While this approach is more powerful and flexible, for this specific problem the mathematical formula from Approach 2 is cleaner and faster. The digit DP approach shines when the problem has additional constraints.
The digit DP approach systematically explores all possible numbers from 0 to n by building them digit by digit. The tight flag ensures we never exceed n. At each position, when we place a digit 1, we know exactly how many numbers share that choice: if we are no longer tight, all 10^(remaining) combinations are valid. If we are still tight, only the numbers up to the remaining part of n are valid.
Memoization ensures we do not recompute the same subproblems. Since there are only O(log n) positions and 2 states for tight, the total number of unique states is O(log n), and each state does O(10) work, giving us O(log n) overall.
Algorithm
- Convert n to an array of digits.
- Define a recursive function
dp(position, tight)that returns the total count of 1s from this position onward across all valid numbers. - At each position, try placing digits 0 through the limit (digit of n if tight, 9 otherwise).
- When placing digit 1:
- If not tight afterward, this 1 appears in 10^(remaining positions) numbers.
- If still tight, compute how many valid numbers remain by looking at the remaining digits of n.
- Recursively add the 1s contributed by future positions.
- Memoize on (position, tight) to avoid redundant computation.
Example Walkthrough
Code
- Time Complexity: O(log n). There are O(log n) digit positions, each with 2 possible tight states. For each state, we iterate over at most 10 digit choices.
- Space Complexity: O(log n). The memoization table stores O(log n) states. The recursion depth is also O(log n).