# Sum of all Subarrays 1

Hello Everyone,

Given an integer array ‘arr[]’ of size n, find sum of all sub-arrays of given array.

Examples :

Input : arr[] = {1, 2, 3}
Output : 20
Explanation : {1} + {2} + {3} + {2 + 3} +
{1 + 2} + {1 + 2 + 3} = 20

Input : arr[] = {1, 2, 3, 4}
Output : 50

Method 1 (Simple Solution)
A simple solution is to generate all sub-array and compute their sum.

Below is the implementation of above idea.

`// Simple C++ program to compute sum of`

`// subarray elements`

`#include<bits/stdc++.h>`

`using` `namespace` `std;`

`// Computes sum all sub-array`

`long` `int` `SubArraySum(` `int` `arr[], ` `int` `n)`

`{`

` ` `long` `int` `result = 0,temp=0;`

` ` `// Pick starting point`

` ` `for` `(` `int` `i=0; i <n; i++)`

` ` `{`

` ` `// Pick ending point`

` ` `temp=0;`

` ` `for` `(` `int` `j=i; j<n; j++)`

` ` `{`

` ` `// sum subarray between current`

` ` `// starting and ending points`

` ` `temp+=arr[j];`

` ` `result += temp ;`

` ` `}`

` ` `}`

` ` `return` `result ;`

`}`

`// driver program to test above function`

`int` `main()`

`{`

` ` `int` `arr[] = {1, 2, 3} ;`

` ` `int` `n = ` `sizeof` `(arr)/` `sizeof` `(arr[0]);`

` ` `cout << ` `"Sum of SubArray : "`

` ` `<< SubArraySum(arr, n) << endl;`

` ` `return` `0;`

`}`

Output:

Sum of SubArray : 20

Time Complexity : O(n2)

Method 2 (efficient solution)
If we take a close look then we observe a pattern. Let take an example

arr[] = [1, 2, 3], n = 3 All subarrays : [1], [1, 2], [1, 2, 3], [2], [2, 3], [3] here first element ‘arr[0]’ appears 3 times second element ‘arr[1]’ appears 4 times third element ‘arr[2]’ appears 3 times Every element arr[i] appears in two types of subsets: i) In subarrays beginning with arr[i]. There are (n-i) such subsets. For example [2] appears in [2] and [2, 3]. ii) In (n-i)i subarrays where this element is not first element. For example [2] appears in [1, 2] and [1, 2, 3]. Total of above (i) and (ii) = (n-i) + (n-i)i = (n-i)(i+1) For arr[] = {1, 2, 3}, sum of subarrays is: arr[0] * ( 0 + 1 ) * ( 3 - 0 ) + arr[1] * ( 1 + 1 ) * ( 3 - 1 ) + arr[2] * ( 2 + 1 ) * ( 3 - 2 ) = 13 + 24 + 3*3 = 20

Below is the implementation of above idea.

`// Efficient C++ program to compute sum of`

`// subarray elements`

`#include<bits/stdc++.h>`

`using` `namespace` `std;`

`//function compute sum all sub-array`

`long` `int` `SubArraySum( ` `int` `arr[] , ` `int` `n )`

`{`

` ` `long` `int` `result = 0;`

` ` `// computing sum of subarray using formula`

` ` `for` `(` `int` `i=0; i<n; i++)`

` ` `result += (arr[i] * (i+1) * (n-i));`

` ` `// return all subarray sum`

` ` `return` `result ;`

`}`

`// driver program to test above function`

`int` `main()`

`{`

` ` `int` `arr[] = {1, 2, 3} ;`

` ` `int` `n = ` `sizeof` `(arr)/` `sizeof` `(arr[0]);`

` ` `cout << ` `"Sum of SubArray : "`

` ` `<< SubArraySum(arr, n) << endl;`

` ` `return` `0;`

`}`

Output :

Sum of SubArray : 20

Time complexity : O(n)