Digit Tally Over a Range

Hard

Write out every integer from lo to hi inclusive in ordinary decimal form, with no leading zeros. How many times does the digit digit appear among all the characters you wrote? Every occurrence counts, even within one number: 22 contains the digit 2 twice. Checking every number is too slow here, since the range can span hundreds of millions of numbers.

Example 1

digit=2, lo=18, hi=23 → 5

The digit 2 appears in 20, 21, 22 (twice) and 23: 5 in total.

Example 2

digit=0, lo=1, hi=30 → 3

Zeros appear only in 10, 20 and 30. Leading zeros are not written, so 7 does not count as 07.

Constraints

0 ≤ digit ≤ 9
1 ≤ lo ≤ hi ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Math Dynamic Programming

Similar problems

How Many Ones Are Written Hard Tasters and the Spoiled Cask Hard Two Groups With the Same Average Hard Prototype Drop Tests Hard Numbers From Working Keys Hard

Input

digit=2, lo=18, hi=23

Expected

Run checks the first 3 tests in your browser. Submit checks all 102 tests on the server, hidden ones included.