2
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • $\begingroup$ What have you tried? Where did you get stuck? We want to help you with your problems, not solve your exercise for you. It's hard for us to know what you don't understand if you don't show us your thought process, what self-study you've done, what reasoning you've tried, and where you got stuck. $\endgroup$ – D.W.♦ Oct 21 '14 at 23:34
1
$\begingroup$

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!

|cite|improve this answer
$\endgroup$
  • $\begingroup$ but how to calculate Noughts(n) in logn time complexity $\endgroup$ – Shahed Al Mamun Oct 21 '14 at 9:05
  • $\begingroup$ so far I know,dp problem has overlapping .where is overlapping in this problwm? $\endgroup$ – Shahed Al Mamun Oct 21 '14 at 9:19
  • $\begingroup$ @Shahedalmamun: you can see the overlapping in the fact that knowing how to solve the problem for $(n,m)$ allows you to solve a part of the problem for $(p,n)$, since $T(n)$ is already computed. To compute $\mathrm{Noughts}(n)$ in $O(\log n)$, simply examine all the digits of $n$ (by dividing it by powers of $10$ and considering the result modulo $10$). $\endgroup$ – zarathustra Oct 22 '14 at 12:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.