Problem Statement:- You are given an array of n integers,a(0) to a(n-1). print the sum of a(i)+a(j) where i<j in O(n) time complexity where n is 1<=n<=10^5.

P.S.:-If not code, Any logical approach will also help me in solving this problem.

Problem Statement:- You are given an array of n integers,a(0) to a(n-1). print the sum of a(i)+a(j) where i<j in O(n) time complexity where n is 1<=n<=10^5.

P.S.:-If not code, Any logical approach will also help me in solving this problem.

If you want sum of a range of elements from index l to r where 0 <= l <= r <= n-1

use segment trees. Sum can be performed in O(log n). You can modify this to find sum of adjacent element.

Tutorials-

Happy coding

Yep, segment trees are good for that. But I need to calculate pairwise sum,and that too better than n^2 approach

You can look for it here. May be it will do. It should work in O(ε log n).

Hey !

Suppose the array is a0 ,a1 , … ,an then summation(ai,aj) such that i<j would be (n-1)*(summation of ai).

Proof:

In the array a0 , a1, a2, … an

a0 can be paired with n-1 terms, ie. a1, a2, a3, … an

a1 can be paired with n-2 terms, ie. a2, a3, a4, … an but a1 already occurred once above with a0

a2 can be paired with n-3 terms, ie. a3, a4, a5, … an but a2 already occurred twice above with a0 and a1

Hence, every element occurs exactly n-1 times in the sum. Thus (n-1)(summation ai).

Example:

Let the array be 1 4 10 5

S(1,4)=5 S(1,10)=11 S(1,5)=6

S(4,10)=14 S(4,5)=9

S(10,5)=15

Hence sum = 60

From my formula above, sum=(n-1)(summation ai) where (summation ai)=(1+4+10+5)=20

Hence sum = (4-1)(20) = 60

pseudocode:

for(i=0;i<n;i++)

sum+=a[i];

cout<<(n-1)*(sum);

Complexity being O(n)!

#lineartime O(n) summationofpairs summation(ai,aj)

2 Likes