Solving a dynamic programming problem?
Let $T(n)$ denote the number of noughts that are necessary to write down all numbers from $0$ to $n$ (included) in base $10$. On input $(n,m)$ ($m&gt;0$), the number you are looking for is then $T(n)-T(m-1)$ (i.e. count the numbers of noughts that you write to go up to $n$, then subtract the ones that you used to go up to $m-1$. The remaining number is the number of noughts that you wrote from $m$ to $n$.), and on input $(n,0)$ the output is simply $T(n)$. It remains to compute the table $T(n)$ quickly enough.

We write $T(0)=1$, and then use the relation $T(n) = T(n-1) + \mathrm{Noughts}(n)$ for $n&gt;0$, where $\mathrm{Noughts}(n)$ denotes the number of noughts needed to write $n$ in base $10$. Given $n$, one can compute all the values of $T$ up to $n$ in time $O(n\log n)$ (the function $\mathrm{Noughts}(n)$, that could be built by examining all the digits of $n$, takes time proportional to $\log n$). Then, for any $0\leq m\leq n$, one can give the output to the problem on $(n,m)$ in constant time!