# UVa 11038

## Summary

Write down all integers between ${\displaystyle m}$ and ${\displaystyle n}$ inclusive (${\displaystyle m\leq n}$) in decimal. How many 0's will you write?

## Explanation

Notation: ${\displaystyle {\overline {a_{n}a_{n-1}\dots a_{0}}}}$ denotes an integer ${\displaystyle a=a_{n}10^{n}+a_{n-1}10^{n-1}+\cdots +a_{0}}$. That is ${\displaystyle a_{n},\ a_{n-1},\ \dots ,\ a_{0}}$ are the decimal digits of ${\displaystyle a}$, from left to right.

Let's solve an easier problem. How many 0's are there in numbers between 0 and ${\displaystyle b}$ inclusive? If we denote this number by ${\displaystyle f(b)}$ then the answer to our original problem is just ${\displaystyle f(n)-f(m-1)}$.

Let ${\displaystyle b={\overline {b_{n}b_{n-1}\dots b_{0}}}}$. Let's find for each position ${\displaystyle 0\leq k how many times a zero appears there as we are counting from 0 to ${\displaystyle b}$.

If ${\displaystyle b_{k}>0}$, then by setting ${\displaystyle a_{k}=0}$, and choosing the other digits according to the constraints: ${\displaystyle 1\leq {\overline {a_{n}\dots a_{k+1}}}\leq {\overline {b_{n}\dots b_{k+1}}}}$, and ${\displaystyle 0\leq {\overline {a_{k-1}\dots a_{0}}}<10^{k}}$, we will have a positive integer ${\displaystyle a={\overline {a_{n}\dots a_{0}}}}$, which is not greater than ${\displaystyle b}$, and the ${\displaystyle k}$-th digit of which exists and is equal to zero. There are ${\displaystyle 10^{k}\cdot {\overline {b_{n}\dots b_{k+1}}}}$ such integers.

If ${\displaystyle b_{k}=0}$, same analysis as above applies, except that when ${\displaystyle {\overline {a_{n}\dots a_{k+1}}}={\overline {b_{n}\dots b_{k+1}}}}$ there are only ${\displaystyle 1+{\overline {b_{k-1}\dots b_{0}}}}$ ways to choose the digits to the right of ${\displaystyle a_{k}}$. So in this case there are ${\displaystyle (10^{k})\cdot ({\overline {b_{n}\dots b_{k+1}}}-1)+1+{\overline {b_{k-1}\dots b_{0}}}}$ integers between 0 and ${\displaystyle b}$, in which the ${\displaystyle k}$-th digit is zero.

The total number of zeroes is the sum of the number of times a zero occurs in each position, plus 1 for the integer "0".

## Input

10 11
100 200
0 500
1234567890 2345678901
0 4294967295
1001010101 1010101010
3020203 302010203
-1 -1


## Output

1
22
92
987654304
3825876150
23709830
231396207