# UVa 11038

## 11038 - How Many 0's[edit]

## Summary[edit]

Write down all integers between and inclusive () in decimal. How many 0's will you write?

## Explanation[edit]

Notation: denotes an integer . That is are the decimal digits of , from left to right.

Let's solve an easier problem. How many 0's are there in numbers between 0 and inclusive? If we denote this number by then the answer to our original problem is just .

Let . Let's find for each position how many times a zero appears there as we are counting from 0 to .

If , then by setting , and choosing the other digits according to the constraints: , and , we will have a positive integer , which is not greater than , and the -th digit of which exists and is equal to zero. There are such integers.

If , same analysis as above applies, except that when there are only ways to choose the digits to the right of . So in this case there are integers between 0 and , in which the -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[edit]

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

## Output[edit]

1 22 92 987654304 3825876150 23709830 231396207