sum of product of all pairs of elements in two arrays

Question

If we have two arrays say 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 sum of product of all possible pairs in both arrays which may be of different lenghts. Of course we can do it in O(n^2) but is there any efficient way to do it ? Thanks. Also both the arrays have integers in the range 1..m and 1..n respectively

Answer 1

This can be done in O(n+m) time by levying the distributive property of multiplication over addition.

The required sum can be generalized 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 factor out the element of B. The series then 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 the elements in A is a factor of each term in the above series, which can be factored out to give

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

We can thus compute the sum of elements of both the arrays and multiply them together to obtain the sum of the series.