CODEWITHSUNDEEP
arraysalgorithm
WillMcavoy
WillMcavoy

Reputation: 1815

Summation of product of all pairs of array elements

If an array has [10,20,30,40]. I need to calculate 10 *20+10*30+10*40+20*30+20*40+30*40. Assuming that both multiplication and addition take constant time. Is it possible to evaluate it using O(n)?

Upvotes: 0

Views: 1475

Answers (2)

Amisha Sahu
Amisha Sahu

Reputation: 89

Explanation: sum of product of all pairs=((sum of numbers)-(sum of square of numbers)^2))/2

int arr[4]={10,20,30,40};
int sum=0,sum_sq=0;
for(int i=0;i<4;i++)
{
    sum+=arr[i];
    sum_sq+=(int)pow(arr[i],2);
}
cout<< ((int)pow(sum,2)-sum_sq)/2;

Output:

3500

Upvotes: 0

David Eisenstat
David Eisenstat

Reputation: 65447

Sure.

def sumproductsofpairs(lst):
    total = 0
    psum = 0
    for x in lst:
        total += psum * x
        psum += x
    return total

Upvotes: 1

Related Questions