863. Ones Written Out
A printer prints every whole number from 1 up to n in ordinary decimal notation, one after another. The ink technician wants to know how many times the digit 1 is printed in total, counting every occurrence in every number (so the number 11 contributes two, and 101 contributes two).
Given n, return that total count. A simple loop over all numbers is too slow when n reaches one billion, so work digit position by digit position: for each place value, decide how many numbers have a 1 in exactly that place.
Example 1
- Input:
- n = 25
- Output:
- 13
- Explanation:
The digit 1 appears once in 1, ten times as the tens digit of 10..19, once more in 11's units digit, and once in 21, giving 13 altogether.
Example 2
- Input:
- n = 105
- Output:
- 27
- Explanation:
Units digit is 1 in 11 numbers (1, 11, ..., 101), tens digit is 1 in 10 numbers (10..19), hundreds digit is 1 in 6 numbers (100..105), total 27.
Constraints
- 1 ≤ n ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 400 msC++ 100 msJava 200 msJavaScript 200 msTypeScript 200 ms
Expected complexity
- Time
- O(log n)
- Space
- O(1)