Array multiplication

[tomtran3110]

I want to multiply every 2 elements in an array then add it all up. And this array is pretty large so O(n^2) will fail. I think I should use divide and conquer method to solve this but I don't really know where to cut it.

  Array[4] = {1, 2, 4, 6}
  Answer = 56

My O(n^2) code would be like:

  for(int i=0; i<n; i++){
    for(j=i+1; j<n; j++){
      answer += arr[i]*arr[j];
    }
  }

I got a hint that says "you can count many pairs a time, all pairs will be considered without going through every single pair." I've been trying to figure out how since yesterday, but I haven't got a clue how to simultaneously do it.

[keskiverto]

Hmm, you have {a, b, c, d} and compute elements of matrix:

a*a a*b a*c a*d
    b*b b*c b*d
        c*c c*d
            d*d

(Which does not produce 56, btw.)

In math:

x*y + x*z == x*(y+z)

The latter form clearly "does multiple (two) pairs" with one multiplication.

In the above you might see:

a*(a)
b*(a+b)
c*(a+b+c)
d*(a+b+c+d)

If only you could accumulate that sum-term alongside of iterating your array and computing the answer ...

(It is indeed doable.)

[Arslan7041]

@Keskiverto: I think you misunderstood the question. An element will not be multiplied by itself.

Thus it would be:

a*b  a*c  a*d
...
...

which does in fact result in 56.

[Arslan7041]

#include <iostream>
#include <algorithm>

int main()
{
    int arr[] = {1, 2, 4, 6};
    int SIZE = sizeof(arr)/sizeof(arr[0]);

    int sumArr = std::accumulate(arr, arr + SIZE, 0); // sum of entire array

    int mySum = 0;

    for(int i = 0; i < SIZE - 1; i++)
    {
        sumArr -= arr[i]; // take away current element from sum of array
        mySum += arr[i]*sumArr; // multiply element by sum of the rest of the array
    }

    std::cout << "The result is: " << mySum << std::endl;
}

[keskiverto]

@Arslan7041: No. I simply did play along with the posted code, whether it matches the actual problem or not.

We do not actually need that std::accumulate here. One loop is enough.

[Arslan7041]

@Arslan7041: No. I simply did play along with the posted code, whether it matches the actual problem or not.

I see. I did the opposite, went along with the answer and disregarded the code.

We do not actually need that std::accumulate here. One loop is enough.

Good idea.

#include <iostream>
#include <algorithm>

int main()
{

    int arr[] = {1, 2, 4, 6};
    int SIZE = sizeof(arr)/sizeof(arr[0]);

    int sumArr = 0;
    int mySum = 0;

    for(int i = 0; i < SIZE-1 ; i++)
    {
        sumArr += arr[i];
        mySum += sumArr*arr[i+1];
    }

    std::cout << "The result is: " << mySum << std::endl;
}

[tomtran3110]

My mistake for typing it wrong!! And thanks for the advice.