Adding each subset of two times

Question

I have an array with elements {7,2,1}, and the idea is to make 7 * 2 + 7 * 1 + 2 * 1, which is basically this algorithm:

for(int i=0;i<n-1;++i) for(int k=i+1;k<n;++k) sum += a[i] * a[k]; 

Where a is an array in which I have numbers and n is the number of elements, I need a more efficient algorithm for this, and I don’t know how to do this, can someone give me a hand?

Thanks!

Answer 1

You can do better in the general case. It's time to do some math. Let's look at the 3-element version:

 ab + ac + bc = 1/2 * (2ab + 2ac + 2bc) = 1/2 * (2ab + 2ac + 2bc + a^2 + b^2 + c^2 - (a^2 + b^2 + c^2)) = 1/2 * ((a+b+c)^2 - (a^2 + b^2 + c^2)) 

I.e:

 int sum = 0; int sum_sq = 0; for (int i : arr) { sum += i; sum_sq += i*i; } int result = (sum*sum - sum_sq) / 2; 

This is O(n) multiplication instead of O(n^2) . This will certainly be better than a naive implementation at some point. Whether this is best for 3 elements is what I did not timed.

Answer 2

The @chux clause is essentially a redistribution of operations:

a _i * a _{i + 1} + a _i * a _{i + 2} + ... + a _i * a _n

->

a _i * (a _{i + 1} + ... + a _n )

combined to avoid unnecessary recalculation of partial sums (a _{i + 1} + ... + a _n ) of terms, using the fact that each is different from the next in the value of one element of the input array.

Here's a one-pass implementation with O (1) overhead:

 int psum(size_t n, int array[n]) { int result = 0; int rsum = array[n - 1]; for (int i = n - 2; i >= 0; i--) { result += array[i] * rsum; rsum += array[i]; } return result; } 

The sum of all elements to the right of index i supported from iteration to iteration in the rsum variable. There is no need to track its various values ​​in the array, because we need each value for only one iteration of the loop.

This scales linearly with the number of elements in the input array. You will see that the number and type of operations are very similar to @Barry's answer, but nothing similar to his last step is required, which saves a few operations.

As @Barry notes in the comments, iteration can also be performed in a different direction, combined with tracking left partial sums taking into account right ones. This will differ from the @chux description, but it is based on the same principles.

Answer 3

Make 1 pass, go from the end [a] to the front and form the sum of all the elements "to the right."

Second pass, Several a[i] * sum[i] .

O (n).

 long sum0(int a[], int n) { long sum = 0; for (int i = 0; i < n - 1; ++i) for (int k = i + 1; k < n; ++k) sum += a[i] * a[k]; return sum; } long sum1(int a[], int n) { int long sums[n]; sums[n - 1] = 0; for (int i = n - 2; i >= 0; i--) { sums[i] = a[i+1] + sums[i + 1]; } long sum = 0; for (int i = 0; i < n - 1; ++i) sum += a[i] * sums[i]; return sum; } void test(int a[], int n) { long s0 = sum0(a, n); long s1 = sum1(a, n); if (s0 != s1) printf("%9ld %9ld\n", s0, s1); } void tests(int k) { while (k--) { int n = rand() % 10 + 2; int a[n + 1]; for (int m = 0; m < n; m++) a[m] = rand() % 256; test(a, n); } } int main() { int a[3] = { 7, 2, 1 }; printf("%d\n", sum1(a, 3)); tests(1000000); puts("Done"); } 

As it turned out, the sums[] array is not needed, since working sums needs only 1 location. This effectively makes the answers look like others.

 long sum1(int a[], int n) { int long sums = 0; long sum = 0; for (int i = n - 2; i >= 0; i--) { sums = a[i+1] + sums; sum += a[i] * sums; } return sum; } 

Answer 4

We have (a + b + c + ...) ² = (a ² + b ² + c ² + ...) + 2 (ab + bc + ca + ...)

You want to get the sum S = ab + bc + ca + ..., which has pairs O (n ² ) (using 2 nested loops)

You can make 2 divided loops, one calculates P = a ² + b ² + c ² + ... in O (n), and the other calculates Q = (a + b + c + ...) ² also in O ( n) time. Then we take S = (Q - P) / 2.