Count total digits written from 1 to n
Filed under Zoho
Free read 3 of 3Confirm input bounds and verify if the output requires counting individual character occurrences or the total count of digits.
The question
Calculate the total number of digit characters written down when listing every integer from 1 to n inclusive.
Constraints
- 1 <= n <= 10^8
- Time complexity must be better than O(n)
Examples
- Input
- n = 13
- Output
- 17
- Why
- Numbers 1 to 9 have 9 digits. Numbers 10 to 13 have 4 numbers * 2 digits = 8 digits. Total = 9 + 8 = 17.
Approach
Confirm input bounds and verify if the output requires counting individual character occurrences or the total count of digits.
Loop from 1 to n, convert each number to a string, and sum their lengths. O(n * log10(n)) time, too slow for large n.
Count digits place by place (units, tens, hundreds) by analyzing ranges and contributions of each power of 10 in logarithmic time O(log10(n)).
Handle n = 0 (if allowed) or small values like n = 1 correctly.
Tips
- What they are testing: Test with powers of 10 (e.g., 9, 10, 99, 100) where digit boundaries shift.
- Common mistake: Iterating linearly up to n, which causes a Time Limit Exceeded (TLE) error for large constraints like 10^8.
Related Zoho questions
Collected from public candidate posts and coding forums. Updated Nov 2026.