I precalculated digits for segment from 1e5 to 2e5, then i computed all digits from 1 to 1e5(if n >= 1e5), then i stepped from 1e5 to n with step size = 1e5. And after all this I computed digits from last step to n. It does about 1e9/1e5 steps and works 0.015 sec.

I think that it's dumb solution, so I want to know, how to solve this task in O(log10(n)) or smth similar.

Two ways I know -

1) Solve for each number of digits
2) Better way (hint): 1 to 10, 11 to 20, etc. each digit is counted once in the ones place

Edited by author 10.10.2023 12:37

Edited by author 10.10.2023 12:37