Jimmy writes down the decimal representations of all natural numbers between and including m and n, (m ≤ n). How many zeroes will he write down?
Input Input starts with an integer T (≤ 11000), denoting the number of test cases.
Each case contains two unsigned 32-bit integers m and n, (m ≤ n).
Output For each case, print the case number and the number of zeroes written down by Jimmy.
Sample Input Output for Sample Input
5
10 11
100 200
0 500
1234567890 2345678901
0 4294967295
Case 1: 1
Case 2: 22
Case 3: 92
Case 4: 987654304
Case 5: 3825876150
what will be the dp states ? as i used the concept of Digit dp , so my states are dp[my current position][my last number][is the number started][is my current digit equal to my target digit] but i am getting correct output for 1st 3 cases, is there anything i am missing ?
This algorithm should work, correct me if there are any mistakes. I will solve for 1 to n, you know how to fit this to your problem:
If number is ending with 9, then you can divide numbers from 0 to N (here you have to add additional case for 0 i.e. if m=0, then add 1 to answer) to 10 equal parts such that numbers in i'th part ends with digit i. Let solve(n) mean count of zeros from 1 to n. Then for each part there are solve(n/10) zeros besides part with 0 digit, though there are solve(n/10)+(n/10). (because of trailing 0's)
Otherwise, it is simple, answer is (count of zeros in n) + solve(n-1). This algorithm works in O(logN) with small constant.
Here is little C++ code:
can you please elaborate the line "Then for each part there are solve(n/10) zeros besides part with 0 digit, though there are solve(n/10)+(n/10). (because of trailing 0's)" , i didn't understand it
If number is not ending by 0, then obviously answer for that is solve(n/10) (because last digit doesn't matters)
If number is ending by 0, then answer is that is solve(n/10) + (n/10), because there are n/10 numbers with ending 0 additionally.
if you don't mind, you can submit your code in this link http://www.lightoj.com/volume_showproblem.php?problem=1140
Got AC.