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 –

 

Download   Run Code

Output:

Index is 2

 
1 Star2 Stars3 Stars4 Stars5 Stars (4 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
AJ
Guest