Addition of every subset of two multiplied

Question

I have an array with the elements {7,2,1} and the idea is to do 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 the array in which I have the numbers and n is the number of elements, I need a more efficient algorithm for doing this, and I have no clue how to do it, can someone give me a hand?

Thank you!

Answer 1

You can do better in the general case. Time to do some math. Let's look at the 3-element version, we have:

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

That is:

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) multiplications, instead of O(n^2). This'll certainly be better than the naive implementation at some point. Whether or not it's better for just 3 elements is something I haven't timed.

Answer 2

@chux's suggestion is essentially to redistribute operations:

a_i * a_{i + 1} + a_i * a_{i + 2} + ... + a_i * a_n

-->

a_i * (a_{i + 1} + ... + a_n)

combined with the avoiding unnecessary recomputation of partial sums of the (a_{i + 1} + ... + a_n) terms by leveraging the fact that each differs from the next by 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 is maintained from iteration to iteration in variable rsum. It's unnecessary to track its various values in an array, because we need each value only for one iteration of the loop.

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

As @Barry observes in comments, the iteration can also be run in the other direction, in conjunction with tracking the left-hand partial sums intead of the right-hand ones. That would diverge a bit more from @chux's description, but it relies on exactly the same principles.

Answer 3

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

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

You can do 2 separated loops, one calculates P = a² + b² + c² + ... in O(n) time, and another calculates Q = (a + b + c + ...)² also in O(n) time. Then take S = (Q - P) / 2.

Answer 4

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

2nd pass, Multiple 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 turns out the sums[] array is not needed either as the the running sums needs only 1 location. This effectively makes this answers similar to 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;
}