Find the sum of i × (number of digits in i) for all L ≤ i ≤ R.
There are maximum 109 integers in the the segment[L, R] so simply considering all the integers one by one will exceed the given time limit.
We break the segment [L, R] into several segments of the numbers with the same number of digits.
For example [10, 9900] = [10, 99] + [100, 999] + [1000, 9900].
If L and R have the same number of digits then the sum for the segment [L, R] will be (number of digits of L) × (L + R) × (R - L + 1) / 2.
There are many way to solve this problem but the most important thing is to find an efficient one.
You can refer to my pseudo code below:
U = L Res = 0 WHILE (U ≤ R) V = min( (10 ^ (number of digits of U)) - 1, R); Res = Res + (number of digits of U) × (U + V) × (V - U + 1) / 2 U = V + 1 ENDWHILE
We do not directly break the segment [L, R] but find the intersection of it with the segments [1, 9], [10, 99], [100, 999] and so on.
There are only 10 segments where the ith segment contains all the positive i-digit integers.