1832. Digit Tally Up To N
A printer numbers pages from 1 to limit and wants to know how much ink one numeral needs. Write every integer from 1 to limit in ordinary decimal, with no leading zeros, and count how many times the digit digit appears in total across all of them. For example, written out from 1 to 13, the digit 1 appears six times: in 1, 10, 11 (twice), 12 and 13.
Return that total as a long. The digit can be 0, and leading zeros are never written, so they must not be counted. Aim for O(log limit) time. Looping over every number from 1 to limit is far too slow for the largest inputs.
Example 1
- Input:
- limit = 13, digit = 1
- Output:
- 6
- Explanation:
Written from 1 to 13, the digit 1 appears in 1, 10, 11 (twice), 12 and 13, which is six times.
Example 2
- Input:
- limit = 100, digit = 0
- Output:
- 11
- Explanation:
The numbers 10, 20, ... 90 contain one zero each, and 100 contains two, so the total is 11.
Example 3
- Input:
- limit = 25, digit = 2
- Output:
- 9
- Explanation:
The digit 2 appears in 2, 12, and in 20 to 25 where 22 has two of them, so the total is 1 + 1 + 7 = 9.
Constraints
1 ≤ limit ≤ 1015
0 ≤ digit ≤ 9
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 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(log limit)
- Space
- O(1)