I am quite new to DP. I thought of an idea to calculate nCr by DP and then calculate the number of zeroes from 0 to n and 0 to m-1. Then the answer would be zeroes(n) — zeroes(m-1). But I saw some solutions that solved this problem in totally different way of DP. I could not get the idea clear. Could you please help me out? TIA.
Problem link: LightOJ — 1140 — How Many Zeroes?
Problem Statement:
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
5 10 11 100 200 0 500 1234567890 2345678901 0 4294967295
Output for Sample Input Case 1: 1 Case 2: 22 Case 3: 92 Case 4: 987654304 Case 5: 3825876150