Split an array into two equal Sum subarrays

This question asked in Facebook and Google and many more good tech company's….

Given an array of integers greater than zero, find if it is possible to split it in two subarrays (without reordering the elements)

Examples :

Input : Arr[] = { 1 , 2 , 3 , 4 , 5 , 5  }
Output : { 1 2 3 4 }
{ 5 , 5 }
Input : Arr[] = { 4, 1, 2, 3 }
Output : {4 1}
{2 3}
Input : Arr[] = { 4, 3, 2, 1}
Output : Not Possible...

Approch-1 :- Brute-Force Solution: Time=O(n²) & Space=O(1)

private static int findSplitPoint(int arr[], int n) {  int leftSum = 0 ;  for (int i = 0; i < n; i++) {    leftSum += arr[i] ;
int rightSum = 0 ;
for (int j = i+1 ; j < n ; j++ )
rightSum += arr[j] ;
if (leftSum == rightSum)
return i+1 ;
}
}

Approch-2 :- Time=O(n) & Space=O(1)

private static int pointToSplitIntoTwoArrays(int arr[], int n) {   int leftSum = 0;   for (int i = 0 ; i < n ; i++) 
leftSum += arr[i];
int rightSum = 0; for (int i = n-1; i >= 0; i--) { rightSum += arr[i];
leftSum -= arr[i] ;
if (rightSum == leftSum)
return i ;
}
return -1;
}

Full Stack Software Developer| Programming enthusiast | Loves DS-Algo and System Design

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store