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

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;
}

Output

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;
}

Output

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)

Output

2

People are also reading:

• Find all symmetric pairs in an array of pairs
• Sort elements by their frequency and index
• Quicksort algorithm using Hoare’s partitioning scheme
• Find a Pair with the given sum in a BST
• Create a mirror of an m–ary Tree
• Construction of an Expression Tree
• Dutch National Flag Problem
• Find Maximum Subarray Sum
• Maximum Sum Circular Subarray
• Find dropping point of an egg