First lets prove that an array can be split at only one point:
E.g
Array = [……….17……….19]
Lets say its split able at 19. To be also split able at 17, the sum of numbers b/w 19 and 17 would have to be -ve(-2 in this case). Which means sum total going from 17 to 19 would be < 17 (=15 in this case). So array would not be split able at 19.
Same can be proven if there is a num > 19 say 23
Now, for quickest run time, we’ll use an extra array to hold the sums.(S)
Algo would be:
Going forward, add and store the sum till that idx i into S[i].
Once the end is reached, walk backward, adding the sum of terms from back
and compare with the sum from front (S[i]
If match found, return true, else return false
Run time would be O(n)
Code(C++):
#include <iostream>
#include <map>
#include <tr1/unordered_map>
#include <tr1/unordered_set>
using namespace std;
using namespace tr1;
bool isSplittable(int *A, int size){
if(size < 2){return false;}
//array to hold sums
int *S = new int[size];
S[0] = A[0];
int i = 1;
int bkwd_sum = A[size-1]; //to hold sum while walking backwards
int fwd_sum = 0;
//put forward sum into S from 0 to len - 1
//cout << "S[0]" << S[0] << endl;
while(i<size-1){
//cout << "i: " << i << endl;
//cout << "A[i] " << A[i] << endl;
S[i] = S[i-1] + A[i];
//cout << "S[i] " << S[i] << endl;
i++;
}
i--;
//cout << "==============================" << endl;
//Start walking backwards till a match in sum is found
while(i>0){
fwd_sum = S[i];
//cout << "i: " << i << endl;
//cout << "bkwd_sum: " << bkwd_sum << endl;
//cout << "fwd_sum "<< fwd_sum << endl;
if(fwd_sum == bkwd_sum){
cout << "array can be split at idx:" << i << endl;
return true;
}
bkwd_sum = bkwd_sum + A[i];
i--;
}
return false;
}
int main (int argc, char * const argv[]) {
int a[7] = {5, 7, 10, 10, -30, 17, 19};
int size = sizeof(a)/sizeof(int);
isSplittable(a, size);
return 0;
}
