The sum of the product of all pairs of elements in two arrays

Question

If we have two arrays: A=[1,2,3,4] and B=[1,2,3] , we need to find the sum 1*1+1*2+1*3+2*1+2*2+2*3+3*1+3*2+3*3+4*1+4*2+4*3 , i.e. the sum of the product of all possible pairs in both arrays, which can have different lengths. Of course, we can do this in O(n^2) , but is there an efficient way to do this? Thank you Both arrays also have integers in the range 1..m and 1..n respectively

Answer 1

This can be done O(n+m) times by running the distributive property of multiplication by adding.

The required amount can be summarized as follows:

 (A[0]*B[0] + A[1]*B[0] + ... + A[m-1]*B[0]) + (A[0]*B[1] + A[1]*B[1] + ... + A[m-1]*B[1]) + ... + (A[0]*B[n-1] + A[1]*B[n-1] + ... + A[m-1]*B[n-1]) 

Note that in each partial sum we can expand the element B Then the series simplifies to

 (A[0] + A[1] + ... + A[m-1]) * B[0] + (A[0] + A[1] + ... + A[m-1]) * B[1] + ... + (A[0] + A[1] + ... + A[m-1]) * B[n-1] 

Note that the sum of all elements from A is a factor of each term in the above series, which can be taken into account to give

 (A[0] + A[1] + ... + A[m-1]) * (B[0] + B[1] + ... + B[n-1]) 

Thus, we can calculate the sum of the elements of both arrays and multiply them together to get the sum of the series.

Answer 2

 1*1+1*2+1*3+2*1+2*2+2*3+3*1+3*2+3*3+4*1+4*2+4*3 =60 (1+2+3) * (1+2+3+4) =60 

Why?

 sum(B) + 2*sum(B) + 3*sum(B) + 4*sum(B) sum(B) * sum(A) 

Answer 3

We can observe the following fact:

 A = [1,2,3,4]; B = [1,2,3]; A * B = A[0] * B[0] + A[0] * B[1] + A[0] * B[2]+ .. + A[3] * B[0] + A[3] * B[1] + A[3] * B[2] = A[0] * (B[0]+B[1]+B[2]) + .. + A[3] * (B[0]+B[1]+B[2]) = (A[0] + A[1] + A[2] + A[3]) * (B[0] + B[1] + B[2]) 

Answer 4

As others have said, you can rewrite your formula as the product of the sums of your vectors.

I'm not sure if your arrays contain arbitrary values ​​in the range 1 ... n or the exact range. If they contain all the elements in the range 1 ... n, you can rewrite sum of 1...n as n*(n+1) / 2