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