CODEWITHSUNDEEP
arraysalgorithm
Mayank Joshi
Mayank Joshi

Reputation: 57

Sum of all the elements of 3 different arrays

I want and optimized algorithm to find sum of each and every element of array.

for example let 3 array:

a = [1,2,3,4];
b = [5,6];
c = [8,9];

then final sum will be equal to:

sum(1,5,8)+sum(1,5,9)+sum(1,6,8)+sum(1,6,9)+sum(2,5,8)...+sum(4,6,9)

I tried doing but the algorithm I used had time complexity O(n^3), so I want anything less than this complexity.

Here is my algorithm:

sum = 0    
for(i=0;i<a.size();i++)
       for(j=0;j<b.size();j++)
          for(k=0;k<c.size();k++)
              sum = sum+a[i]+b[j]+c[k];

Upvotes: 1

Views: 627

Answers (2)

Sufian Latif
Sufian Latif

Reputation: 13356

For this example, a, b and c have 4, 2 and 2 elements respectively. If you want to add them in every combination, there will be 4 * 2 * 2 = 16 terms to add. In those terms, each element of a will appear 4 times, because it will be added to 2 * 2 = 4 combinations of elements of b and c. Similarly, each element of b (or c) will appear 8 times, because it will be added to each 4 * 2 = 8 combinations of each elements of a and c (or b).

So, in the final sum, each element of a will appear 4 times and each element of b and c will appear 8 times. Once you figure that out, you can do fewer number of multiplications and additions to get the result.(Just sum of elements of individual arrays and then multiply these sums by 4 , 8 and 8 respectively).

Upvotes: 3

Bernhard Barker
Bernhard Barker

Reputation: 55609

Each element of a will appear in sums with each element of b and each element of c.

This means that every element in a will appear in a number of sums equal to b.length * c.length.

This is also easy to see from the brute force pseudo-code: (modified for readability)

for i = 0 to a.length
   for j = 0 to b.length     // happens once for each i
      for k = 0 to c.length  // happens b.length times for each i
         sum += a[i] + ...   // happens b.length * c.length times for each i

Generalising this, we come up with the following algorithm:

  • Sum all elements a, multiply the result by b.length * c.length.
  • Sum all elements b, multiply the result by a.length * b.length.
  • Sum all elements c, multiply the result by a.length * b.length.
  • Return the above three values added together.

This is an O(n) algorithm, where n is the total number of elements or average number of elements per array.

Upvotes: 0

Related Questions