Number of Digit One — Solution in Python, Java & C++
Number of Digit One solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem on math and recursion.
Number of Digit One is a hard coding problem on math, recursion and Digit DP, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Hard
- Topics: Math, Recursion, Digit DP
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Count the total number of digit 1 characters that appear across all the integers from 1 to n inclusive.
Example 1
Input: n = 13
Output: 6
Explanation: The ones appear in 1, 10, 11 (twice), 12 and 13.
Example 2
Input: n = 0
Output: 0
Example 3
Input: n = 100
Output: 21
Constraints
0 <= n <= 1000000000
Hints for Number of Digit One
Hint 1
Count the ones position by position: how many numbers in
[1, n]have a1in the units place, the tens place, and so on.Hint 2
Split
nat the positionpintohigher = n / (10p), the digit atp, andrest = n mod 10p.Hint 3
The full higher blocks contribute
higher * p, and the partial block contributesmin(max(rest - p + 1, 0), p).
How to solve Number of Digit One
Fix a digit position p (1, 10, 100, …) and count how many integers in [1, n] carry a 1 there. Summing over positions gives the total, with no enumeration at all.
Approach
- For each power of ten
pup ton, lethigher = n / (10p)andrest = n % (10p). - Every complete higher block contributes exactly
pnumbers with a1at positionp— that ishigher * p. - The partial block contributes
rest - p + 1, clamped to the range[0, p]. - Add both parts and move to the next position.
Why it works
Within each span of 10p consecutive integers, exactly p of them have a 1 at position p — the ones whose value at that position equals 1. The clamp handles the final, possibly incomplete span: rest below p contributes nothing, rest at or above 2p - 1 contributes a full p, and in between it contributes the partial count.
Complexity
- Time —
O(log n) - Space —
O(1)
Pitfalls
p * 10overflows 32 bits oncepreaches10^9; carry the powers in 64 bits or stop the loop atp > n / 10.- Enumerating
1..nand counting characters isO(n log n)and far too slow at the stated limit. - Forgetting the clamp double counts the partial block on inputs like
n = 12.
Reference solution
Python
def countDigitOne(n: int) -> int:
total = 0
p = 1
while p <= n:
higher = n // (p * 10)
rest = n % (p * 10)
total += higher * p + min(max(rest - p + 1, 0), p)
p *= 10
return totalJava
public static int countDigitOne(int n) {
long total = 0;
for (long p = 1; p <= n; p *= 10) {
long higher = n / (p * 10);
long rest = n % (p * 10);
total += higher * p + Math.min(Math.max(rest - p + 1, 0), p);
}
return (int) total;
}C++
int countDigitOne(int n) {
long long total = 0;
for (long long p = 1; p <= n; p *= 10) {
long long higher = n / (p * 10);
long long rest = n % (p * 10);
long long partial = rest - p + 1;
if (partial < 0) partial = 0;
if (partial > p) partial = p;
total += higher * p + partial;
}
return (int) total;
}JavaScript
var countDigitOne = function(n) {
var total = 0;
for (var p = 1; p <= n; p *= 10) {
var higher = Math.floor(n / (p * 10));
var rest = n % (p * 10);
total += higher * p + Math.min(Math.max(rest - p + 1, 0), p);
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 337 math problems · the whole catalogue
Learn the technique: Recursion