Spoj Sum of Digits getting TLE,Please help

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.

My sloution O(n) — Brute force appraoch

2 Likes

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

This is pretty straight forward, learn it from here

//