PPNUM - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

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 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.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

1 Like
2

As a trivia, here’s a fun formula for the answer:

Define x and F(n) as:

x = floor[log10(n)]+1 (i.e. x is the number of digits of n) and
F(n) = [n(n-1)x·500000004+(10x-1)(10x-10)·176767678] mod 1000000007

Then the answer for a query [L, R] is [F(R+1) - F(L)] mod 1000000007 :smiley:

(of course, during the contest I didn’t use this formula)

14 Likes
3

sum of numbers in the given interval[L, R] = (L + R) × (R - L + 1) / 2.

how this formula works…?

1 Like
4

I don’t understand the above pseudo code because there the condition while( U<= R ) goes to be infinity loop . Please say if i wrong.

5

Let S = L + (L+1) + (L+2) + ... + (R-2) + (R-1) + R. Then:

S = L + (L+1) + (L+2) + ... + (R-2) + (R-1) + R
S = R + (R-1) + (R-2) + ... + (L+2) + (L+1) + L

Adding term by term, we get:
2S = (L+R) + (L+R) + (L+R) + ... + (L+R) [(R-L+1) times]

So, 2S = (L+R)×(R-L+1), and S = (L+R)×(R-L+1)/2, which is the result we want.

4 Likes
6

I added the line U = V + 1 at the end (which seems to have been omitted).

1 Like
7

Now since, you have shared this, just getting curious if anyone did use this at all…

8

Why am getting time limit exceeded answer please?

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;

class ppnum { public static void main(String[] args)throws NumberFormatException, IOException {

int n,m,j,k,i,len,count=0; BufferedReader s= new BufferedReader(new InputStreamReader(System.in)); n=Integer.parseInt(s.readLine()); if(n>=1 && n<=1000) { int a[][]=new int[n][2]; for(m=0;m<n;m++) { String[] inp = s.readLine().split(" "); a[m][0]=Integer.parseInt(inp[0]); a[m][1]=Integer.parseInt(inp[1]); } for(j=0;j<n;j++) { if(a[j][0]>=1 && a[j][0]<=a[j][1] && a[j][1]<=Math.pow(10, 9)) {
if(a[j][0]<=a[j][1]) { for(i=a[j][0];i<=a[j][1];i++) {
len=Integer.toString(i).length(); count=count+(ilen); } } else
{
for(i=a[j][0];i<=a[j][1];i++) { len=Integer.toString(i).length(); count=count+(ilen); }
} System.out.println(count); count=0;
}
}
}
} }