Number of Digit One
Understanding the Problem
We count every individual occurrence of the digit 1 across all numbers from 0 to n, not how many numbers contain a 1. The number 11 contributes 2, the number 111 contributes 3, and so on.
A brute force approach iterates through every number from 1 to n and counts the 1s in each. With n up to 10^9, that means examining the digits of up to a billion numbers, which is too slow.
A faster approach analyzes each digit position independently. Instead of asking "how many 1s are in number k?", we ask "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, iterating through every number is too slow. Even O(n) is around 10^9 operations. We need O(log n).ncan be 0 → an edge case where the answer is 0.
Approach 1: Brute Force
Intuition
Iterate through every number from 1 to n, break each one into its digits, and count how many of those digits are 1. For each number, we extract digits using modulo and division, checking whether each digit equals 1. This is correct but too slow for the given constraints.
Algorithm
- Initialize
count = 0. - For each number
ifrom 1 ton: - While
i > 0, check ifi % 10 == 1. If so, incrementcount. - Divide
iby 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 too slow. The digit 1 appears in a repeating pattern at each position, so the next approach calculates the count at each position directly from 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 higher part counts how many full groups fit below n, and the current digit determines what the final partial group contributes.
That partial group splits into three cases. If the current digit is 0, the position never reaches 1 in the final partial group, so only the full groups contribute. If it is exactly 1, the final group is partway through the span where this position holds a 1, and that span covers lower + 1 values (0 through lower). If it is 2 or more, the entire span where this position holds a 1 is included, adding one more full group.
Algorithm
- Initialize
count = 0andfactor = 1(starting from the ones place). - While
factor <= n: - Compute
higher = n / (factor * 10)(digits to the left). - Compute
current = (n / factor) % 10(the digit at this position). - Compute
lower = n % factor(digits to the right). - If
current == 0: addhigher * factorto count. - If
current == 1: addhigher * factor + lower + 1to count. - If
current >= 2: add(higher + 1) * factorto count. - Multiply
factorby 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). The next approach reaches the same time complexity with a more general framework, digit dynamic programming, which extends to variations like counting numbers with exactly k ones or other per-digit constraints.
Approach 3: Recursive Digit DP
Intuition
Digit dynamic programming builds every number from 0 to n digit by digit, from the most significant position to the least. At each step it tracks one bit of state: whether we are still "tight" (the digits placed so far match the prefix of n exactly, so the next digit is capped by n) or "free" (we already placed a digit smaller than n's at some earlier position, so every remaining digit can range over 0-9).
At each position we place digits 0 through the limit (the digit of n if tight, 9 otherwise). When we place a 1, we count how many complete numbers include this particular 1. If we become free, the remaining positions can each be 0-9, so this 1 appears in 10^(remaining positions) numbers. If we stay tight, the remaining positions are bounded by the rest of n, so this 1 appears in lower + 1 numbers.
For this specific problem the closed-form formula from Approach 2 is shorter and faster. Digit DP generalizes to problems with extra per-digit constraints, where no simple formula exists.
The tight flag enforces the upper bound: while tight, the next digit cannot exceed the matching digit of n, so no number built by the recursion exceeds n. When we place a digit 1 at a position, the count of complete numbers that contain it equals the number of ways to fill the remaining positions. If we are free, that is 10^(remaining). If we are still tight, the remaining positions are bounded by the suffix of n, giving lower + 1 valid completions.
Memoization on (pos, tight) avoids recomputing the same state. There are O(log n) positions and 2 tight values, so O(log n) distinct states, each doing O(10) work, for 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).