C program to find sum of all sub-array of a given array

In this blog post, we learn how to write a C program to find the sum of all sub-array sums for a given array? So here we will write the C program to find the sum of all sub-array sums for a given array. We will also see how to display the sum of all sub-array sums for a given array using C programming.

 

Example,

//Given array
Input : arr[] = {1, 3, 5} 

Output: 30 

Explanation: All possible sub-array sum is: 
(1) + (3) + (5) + (1+3) + (3+5) + (1+3+5) =>  30

 

Note: A sub-array is a contiguous part of the array. In the above example {1,5} is not a subarray because they’re not consecutive in the array.

 

So let’s see the logic to find the sum of all sub-array sums for a given array. Suppose arr is an integer array of size N (arr[N] ), the task is to write the C program to find the sum of all sub-array sum for a given array.

 

Method 1: By Generating sub array

This method is very simple to calculate the sum of sub-array, in which we will just list off all the subarrays and add all of them up. We can implement this using the triple loop, where we will iterate over all pairs of (start, stop). This technique is very poor and there are several observations. The time complexity of this solution is O(n^3).

#include <stdio.h>

//Calculate array size
#define ARRAY_SIZE(a)  sizeof(a)/sizeof(a[0])


// Computes sum all sub-array
long int subArraySum(int arr[], int n)
{
    long int result = 0;
    int i =0,j=0, k= 0;

    // Pick starting point
    for (i=0; i <n; i++)
    {

        // Pick ending point
        for (j=i; j<n; j++)
        {

            for (k = i ; k <= j ; k++)
            {
                result += arr[k];
            }

        }
    }
    return result ;
}


int main()
{
    int arr[] = { 1,3,5};

    //Get array size
    int n = ARRAY_SIZE(arr);

    //Get sum of all sub array
    long int sum  = subArraySum(arr, n) ;

    printf("Sub Array Sum = %d\n",sum);

    return 0;
}

Output:

sum of sub array in c

 

If you want to learn more about the c language, here 10 Free days (up to 200 minutes) C video course for you.

Your free trial is waiting

 

 

Method 2: Optimized Subarray Enumeration

We can optimize the first solution using the below technique. So let’s see the technique to how we can increase the performance of the above solution.

If you know the sum of the subarray from index ‘i’ to index ‘j’, then then the sum of the subarray from index ‘i’ to index j+1 can be formed by taking the sum of the original subarray, then adding arr[j+1] into the total. The time complexity of this solution is O(n^2).

Example,

//Assumed input integer array
int arr[] = {1,2,3,4,5}

subArray1 > {1,2} and sum is (1+2) => 3
subArray2 > {1,2,3} and sum is (1+2+3) => 6

We can also calculate the sum of subArray2 using the above-described technique.

subArray2 => subArray1 + arr[2] > 3 + 3 > 6

 

 

#include <stdio.h>

//Calculate array size
#define ARRAY_SIZE(a)  sizeof(a)/sizeof(a[0])


// Computes sum all sub-array
long int subArraySum(int arr[], int n)
{
    long int result = 0,temp=0;
    int i =0,j=0;

    // Pick starting point
    for (i=0; i <n; i++)
    {

        temp=0;
        // Pick ending point
        for (j=i; j<n; j++)
        {
            // sum subarray between current
            // starting and ending points
            temp+=arr[j];
            result += temp ;
        }
    }
    return result ;
}


int main()
{
    int arr[] = {1,3,5} ;

    //Get array size
    int n = ARRAY_SIZE(arr);

    //Get sum of all sub array
    long int sum  = subArraySum(arr, n) ;

    printf("Sub Array Sum = %d\n",sum);

    return 0;
}

Output:

sum of sub array in c

 

 

Method 3: Subarray sum using pattern technique

In all mentioned techniques it is the most optimized algorithm to calculate the sum of the subarray. The basic idea behind the approach is to compute the sum, but not in the order intended. For example, take a look at the array [1, 2, 3]. The subarrays are:

//Subarrays of an array {1,2,3},

[1]  [2]  [3] 

[1, 2]  [2, 3]

  [1, 2, 3]

 

Now, notice how many copies of each element there are. There are three 1’s, four 2’s, and three 3’s.

here first element 'arr[0]' appears 3 times  
  
     second element 'arr[1]' appears 4 times  

     third element 'arr[2]' appears 3 times

 

If we could efficiently compute how many copies of each element there are across all the different subarrays, we could directly compute the sum by multiply each element in the array by the number of times it appears across all the subarrays and then adding them up.

If you will analyze the pattern you will find that every element arr[i] appears in two types of subsets:

  1.  In subarrays beginning with arr[i]. There are (n-i) such subsets. For example [2] appears in [2] and [2, 3].
  2.  In (n-i)*i subarrays where this element is not first element. For example [2] appears in  [1, 2] and [1, 2, 3].

 

This means that the total number of intervals overlapping element i is given by,

total number of ith element = (n-i) + (n-i)*i;
                            = (n-i)(i+1);

where n is the size of the array.

 

#include <stdio.h>

//Calculate array size
#define ARRAY_SIZE(a)  sizeof(a)/sizeof(a[0])


long int subArraySum( int arr[], int n )
{
    long int result = 0;
    int i =0;

    // computing sum of sub array using formula
    for (i=0; i<n; i++)
    {
        result += (arr[i] * (i+1) * (n-i));
    }

    return result ;
}


int main()
{
    int arr[] = {1,3,5} ;

    //Get array size
    int n = ARRAY_SIZE(arr);

    //Get sum of all sub array
    long int sum  = subArraySum(arr, n) ;

    printf("Sub Array Sum = %d\n",sum);

    return 0;
}

Output:

sum of sub array in c

 

 

Recommended Articles for you: