Some numbers are called unlucky if their decimal representation contain number $5$.
For example: $123456,245,1555$ are unlucky numbers and $111,123,147$ are not unlucky numbers.
In how many unlucky number in segment $[a;b]?$, where $1\le a\le b$
For example $a=1,b=17$ , we have the result is 2. Because, there are only 5,15.
This is my try: I call $f(a)$ is the amount of unlucky numbers in segment $[1;a]$, then we have $f(a+1)$ is the the amount of unlucky numbers in segment $[1;a+1]$, so we have: $f(a+1)=f(a)$ if $a+1$ is not unlucky number and $f(a+1)=f(a)+1$ if a+1 is unlucky number. My problem is to compute $f(a)$ with $O(log(n))$, but I can't come to finally solution!
Hint: Solve it for numbers from $1$ to $10^n$ first. You should get something like $10^n-9^n$ why?
Then solve it for numbers from $1$ to $a.$ go in the base 10 representation of the number $a$ from left to right. How can you use what you learn in the previous step?
Use this information to solve $[a,b]$ by solving $[1,a]$ minus $[1,b]$