Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Alex writes down the decimal representations of all natural numbers between and including m and n, (m ≤ n). How many zeroes will he write down?
My one friend said to me that this problem can be solved by dynamic programming.But I can't understand how to solve it by dynamic programming .Can someone explain it with great details.Here is some input and output.
1.input:m=10, n=11 and output:1
2.input:m=100,n=200 and output:22
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>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>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!
