Sum of all Subarrays 1

Software Development
#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)