213. Number of Digit One
Imagine writing out every integer from 1 up to n, one after another. How many times does the digit 1 get written in total?
You receive a single non-negative integer n; return the total count of 1 digits across the decimal representations of all integers in the range [1, n].
For instance, up to 13 the digit shows up in 1, 10, 11 (twice), 12, and 13 — six occurrences in all. Note that a number like 11 contributes once per 1 it contains, not once per number.
With n as large as a billion, visiting every number is not an option — the count has to come from arithmetic, not enumeration.
Example 1:
Input: n = 13
Output: 6
Explanation: The digit 1 appears in 1, 10, 11 (which contains it twice), 12, and 13 — a total of 6 times.
Example 2:
Input: n = 99
Output: 20
Explanation: The ones place holds a 1 ten times (1, 11, 21, …, 91) and the tens place ten times (10 through 19): 10 + 10 = 20.
Constraints:
- 0 ≤ n ≤ 10⁹
Hints:
Scanning every number up to 10^9 and counting its digits is hopeless. Flip the question: instead of asking how many 1s each *number* has, ask how many 1s each *digit position* contributes across the whole range.
Fix a place value p (1, 10, 100, …) and split n into higher = n / (10p), cur = (n / p) mod 10, lower = n mod p. If cur > 1, that place shows a 1 exactly (higher + 1)·p times; if cur == 1, it is higher·p + lower + 1; if cur == 0, just higher·p. Sum over all places.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 13
Expected output: 6