### PROBLEM LINK:

**Author:** Vitaliy Herasymiv

**Tester:** Tasnim Imran Sunny

**Editorialist:** Tuan Anh

### DIFFICULTY:

EASY

### PREREQUISITES:

none

### PROBLEM:

Find the sum of **i** × (number of digits in **i**) for all **L** ≤ **i** ≤ **R**.

### EXPLANATION:

There are maximum **10 ^{9}** 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 **i ^{th}** segment contains all the positive

**i**-digit integers.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.