UVa 11038

From Algorithmist
Jump to navigation Jump to search

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 

Implementations[edit]