How Many Ones Are Written

Hard

Write down every integer from 0 to limit inclusive. How many times does the digit 1 appear in all of them together? For example, the number 111 contains three ones. limit can be up to a billion, so writing the numbers out one by one is too slow.

Example 1

limit=12 → 5

Ones appear in 1, 10, 11 (twice) and 12, five in total.

Example 2

limit=9 → 1

Among 0 through 9 there is a single 1.

Example 3

limit=100 → 21

Constraints

0 ≤ limit ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Recursion Math Dynamic Programming

Similar problems

Every Bracketing Result Medium Duel for the End Cards Medium Sum of the Two Before Easy Pattern With Dot and Star Hard Does the Text Fit the Pattern Hard

Input

limit=12

Expected

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