Tally a Digit From One to N
HardMath & Geometry
Problem
A sign-maker prints every house number from 1 to n and needs to know how many copies of one particular digit (0 to 9) to order.
Return how many times digit appears when all integers from 1 to n are written in decimal without leading zeros.
Example 1
- Input:
- n = 13, digit = 1
- Output:
- 6
1, 10, 11 (twice), 12 and 13.
Example 2
- Input:
- n = 25, digit = 2
- Output:
- 9
2, 12, 20, 21, 22 (twice), 23, 24 and 25.
Example 3
- Input:
- n = 100, digit = 0
- Output:
- 11
One zero in each of 10, 20, ..., 90 and two in 100.
Constraints
- 1 ≤ n ≤ 10^15
- 0 ≤ digit ≤ 9
Hint
Show the first hint
Count position by position: how many numbers in 1..n have digit in the units place, in the tens place, and so on?
Walkthrough
How to approach it
01Clarify before coding
- Is 0 itself written? No, the range starts at 1.
- Leading zeros are not written, so 7 does not contain a 0 in its tens place.
- How large is the answer? Up to about 1.5 · 10^15, still a safe integer in JavaScript.
02Brute force
Write every number from 1 to n and count the digit.
Cost: O(n log n): 10^15 numbers.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.