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

Given an array of integers, find an index that divides the array into two non-empty subarrays having equal sum.

For example, consider the array {-1, 6, 3, 1, -2, 3, 3}.

Here index 2 divides it into two non-empty subsets {-1, 6} and {1, -2, 3, 3} having same sum.

Naive solution would to calculate sum of left and right sub-array for each element of the array and print the index if both sums is found to be same. The time complexity of above solution is O(n2).

We can solve this problem in linear time by using extra space. The idea is to preprocess the array and store sum of left and right sub-array of every index in two auxiliary arrays. Then we can calculate left and right sum in constant time for any index.

The problem can also be solved in linear time and constant space. The idea is to preprocess the given array and store sum of all elements present in the array in a variable. Then we traverse the array, and maintain another variable to store left sub-array sum till current element. Now right sub-array sum can be calculated in constant time by using below formula

sum of right subarray = sum of all elements – current element – sum of left subarray

This is demonstrated below in C –

Output:

Index is 2

(4 votes, average: 5.00 out of 5)