Find an element in array such that sum of left array is equal to sum of right array

In this blog post, we learn how to write a C program to find an element in an array such that the sum of the left array is equal to the sum of the right array? So here we will write the C program to find an element in the array such that the sum of the left array is equal to the sum of a right array. We will also see how to display the element from which the sum of the left part of the array and the right part of the array become equal.

 

Suppose arr is an integer array of size N (arr[N] ), the task is to write the C program to Find an element in an array such that the sum of the left array is equal to the sum of the right array.

Example,

Input: 1 4 2 0 5

Output: 2 (You can see the sum of the left and right part of the array is equal).

Left part: {1,4};

Right part: {0, 5};

 

Logic to find an element in array such that sum of left array is equal to sum of right array:

There are many ways to find the element but here I am using the suffix and prefix array concept. So let’s see the concept.

1. Create two arrays of size N ( size of input array) prefixSumArr and suffixSumArr.

2. Initialize prefixSumArr  0th index with input array 0th index.

prefixSumArr[0] = arr[0];

3. Initialize suffixSumArr last index (N-1) with the input array last index (N-1).

4.  Now, we will traverse both arrays. The index at which they yield equal result is the index where the array is partitioned with equal sum.

 

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

 

 

C program to find an element in an array such that the sum of the left array is equal to the sum of the right array:

 

#include <stdio.h>

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

int findElement(int arr[], int n)
{
    int elementNotFound = -1, i =0;
    int prefixSumArr[n];
    int suffixSumArr[n];

    //Initialize prefixSumArr with arr 0th index
    prefixSumArr[0] = arr[0];

    //Initialize suffixSumArr with arr last index (N-1)
    suffixSumArr[n - 1] = arr[n - 1];

    //forming prefix sum array from 0 
    for (i= 1; i < n; i++)
    {
        prefixSumArr[i] = prefixSumArr[i - 1] + arr[i];
    }

    //Forming suffix sum array from n-1
    for ( i = n - 2; i >= 0; i--)
    {
        suffixSumArr[i] = suffixSumArr[i + 1] + arr[i];
    }

    // Find the point where prefix and suffix
    // sums are same.
    for ( i = 1; i < n - 1; i++)
    {
        if (prefixSumArr[i] == suffixSumArr[i])
        {
            elementNotFound = arr[i];
            break;
        }
    }

    return elementNotFound;
}

int main()
{
    int arr[] = {1, 4, 2, 0, 5};

    int N = ARRAY_SIZE(arr);

    printf("%d",findElement(arr, N));

    return 0;
}

Output:

Find an element in array such that sum of left array is equal to sum of right array

 

Recommended Articles for you: