Help needed in one of the Hackerearth Problem!

general
, ,
1

[The furious five | Practice Problems]

I am not getting How to solve this problem and even after watching out the editorials, the solution went out of my head please help.

2

This is just binary search.
We can compute \sum_{x=1}^k f(x) in O(\log k). Let’s replace 5 with 10. The number of times we can divide by 10 is just the number 0s at the end. So for any number x, let us count the sum of number of 0s, for numbers less than x.
x/10 numbers will have the units digit as 0
x/100 numbers will have units and tens digit as 0.
x/1000 number will have hundreds digit 0 as well.

So this is just counting the number of times the units digit, tens digit, and hundreds digit will be counted.

So answer is

x/10 + x/100 + x/1000 ....

Obviously, we are using floor division.

1 Like
3

Thank you so much bro, Got it

4

Can you explain it in detail? I am still unable to understand it.