Sum of all Subarrays

https://www.geeksforgeeks.org/sum-of-all-subarrays/

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

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

= 1*3 + 2*4 + 3*3 
= 20

    public static long SubArraySum( int arr[] , int n )

    {

        long 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 ;

    }

Method 1 (Simple Solution)

Time Complexity : O(n3)

A simple solution is to generate all sub-array and compute their sum.

    public static long SubArraySum(int arr[], int n)

    {

        long result = 0;

       

        // Pick starting point

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

        {

            // Pick ending point

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

            {

                // sum subarray between current

                // starting and ending points

                for (int k = i; k <= j; k++)

                    result += arr[k] ;

            }

        }

        return result ;

    }




https://www.geeksforgeeks.org/sum-of-all-subsequences-of-an-array/

Given an array of n integers. Find the sum of all possible subarrays.

Examples :

Input : arr[] = { 1, 2 }
Output : 6
All possible subarrays are {}, {1}, {2} 
and { 1, 2 }

Let us take a closer look at the problem and try to find a pattern

Let a[] = { 1, 2, 3 }

All subarrays are {}, {1}, {2}, {3}, {1, 2}, 
                     {1, 3}, {2, 3}, {1, 2, 3}

So sum of subarrays are 0 + 1 + 2 + 3 + 3 + 
                             4 + 5 + 8 = 24

Here we can observe that in sum every elements 
occurs 4 times. Or in general every element 
will occur 2^(n-1) times. And we can also 
observe that sum of array elements is 6. So
final result will be 6*4.

In general we can find sum of all subarrays by adding all elements of array multiplied by 2(n-1) where n is number of elements in array.

    static int findSum(int arr[], int n)

    {

        // Sum all array elements

        int sum = 0;

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

            sum += arr[i];

  

        // Result is sum * 2^(n-1)

        return sum * (1 << (n - 1));

    }