# Find the index that divides an array into two non-empty subarrays with equal sum

Posted in

Last updated on July 20, 2024

## Problem

Given an integer array, find an index that divides it into two non-empty subarrays having an equal sum.

#### Sample Input

[9, 2, 4, 5, 6]

#### Sample Output

Index 2 (0-based-indexing) divides the array into [9,2] and [5,6] having equal sum.

### Approach

The approach is to first store the sum of all the elements in a variable named sum . We then traverse through the array and keep track of the prefix sum of each element. The sum of the right subarray of the current element will be sum - prefix sum - current element . If this sum is equal to the prefix sum, then we found the index. The time complexity of this approach is O(N).

#### C Programming

#include <stdio.h>
voidsolve(int arr[], int n)
{
int sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
}
int prefixSum = arr[0];
for (int i = 1; i < n - 1; i++)
{
if (prefixSum == sum - (arr[i] + prefixSum)) {
printf("%d", i);
break;
}
prefixSum += arr[i];
}
}
intmain(void)
{
int arr[] = {9, 2, 1, 5, 6 };
int n = sizeof(arr)/sizeof(arr[0]);
solve(arr, n);
return0;
}

2

#### C++ Programming

#include <bits/stdc++.h>
usingnamespacestd;
voidsolve(int arr[], int n)
{
int sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
}
int prefixSum = arr[0];
for (int i = 1; i < n - 1; i++)
{
if (prefixSum == sum - (arr[i] + prefixSum)) {
cout<<i;
break;
}
prefixSum += arr[i];
}
}
intmain(void)
{
int arr[] = {9, 2, 1, 5, 6 };
int n = sizeof(arr)/sizeof(arr[0]);
solve(arr, n);
return0;
}

2

#### Python Programming

defsolve(arr):
sumArray = sum(arr)
prefixSum = arr[0]
for i in range(1, len(arr) - 1):
if prefixSum == sumArray - (arr[i] + prefixSum):
print(i)
prefixSum += arr[i]
arr = [2, 9, 1, 5, 6]
solve(arr)

2