Hi everyone,
This is the link to the problem in the spoj
Firstly i thought it was an easy problem but later i have got TLE on submitting and then i have observed that the time limit is so less.
My code is of O(n) solution.
Can anyone Please tell me any hint/idea for doing this problem, i would be very much thankful.
Obviously O(n) won’t work for n = 10^9
Try to make a function for the sum of digits of numbers from 1 to n.
Hint: Precompute the value of this function for n of the form k \times 10^i using dp
Since my solution is too messy,I don’t think you’ll be able to understand how I did it just by looking at my code.
So Here’s a simple explantion by an example:
consider A as 5 and B as 243.
My Solution:
I broke 5…243 into three parts-
5…99 100…199 200…243
first part(5…99)-
5…9 10…19 20…29 30…39 and so on upto 90…99
lets take 10…19
1 is repeated 10 times and sum of 0-9 is precomputed and stored
20…29
2 is repeated 10 times and sum of 0-9 is precomputed
and so on…
second part(100-199)-
1 is repeatedd 100 times and sum 0-99 is precomputed.
third part(200-243)-
2 is repeated 44 times and solve for 43 using the same recursion strategy.
Here’s my solution-http://ideone.com/Ix5I8X