Interview Question
Country: United States
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:
#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
while(i<size-1){
S[i] = S[i-1] + A[i];
i++;
}
i--;
//Start walking backwards till a match in sum is found
while(i>0){
fwd_sum = S[i];
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;
}
public static bool IsSplittable(List<int> arr)
{
if (arr == null || arr.Count() == 0)
return false;
int total = arr.Sum();
if(total%2!=0) return false;
int half = (int)(total/2);
arr.Sort();
int st, end, sum;
st = end = sum = 0;
bool endFwd = true;
while (st < arr.Count() && end < arr.Count)
{
if (endFwd)
{
sum += arr[end];
}
else
{
sum -= arr[st - 1];
}
if (sum == half)
return true;
if (sum > half)
{
st++;
endFwd = false;
}
else
{
end++;
endFwd = true;
}
}
return false;
}
Start by accumulating sum of left side elements in "sumLeft". Collect more elements only if sumLeft is smaller than sum of elements to the right of idx till idx < size.
bool isSplittable(int[] arr)
{
int size = sizeof(arr)/sizeof(int);
if(size < 2) return false;
int i=0;
int sumLeft = 0;
while(1)
{
sumLeft += arr[i];
int tmpSum = sumLeft;
for(int idx=i; idx < size; idx++) {
tmpSum -= arr[idx];
}
if (tmpSum == 0) return true;
if (tmpSum < 0) i++;
else return false;
}
return false;
}
Improved/corrected a bit:
// Return true if arr can be divided into two parts having equal sums; return false otherwise.
#include <iostream>
#define PRINT(_X, _size) std::cout << std::endl << "ARRAY = {"; for (int i=0; i < _size; ++i) std::cout << " " << _X[i]; std::cout << " }" << std::endl;
int isSplittable(int *arr, int size)
{
//int size = sizeof(arr)/sizeof(int);
if(size < 2) return -1;
int i=0;
int sumLeft = 0;
while(1)
{
sumLeft += arr[i];
int tmpSum = sumLeft;
for(int idx=i+1; idx < size; idx++) { // O(n log(n)) ???
tmpSum -= arr[idx];
}
//std::cout << "i = " << i << ", tmpSum = " << tmpSum << ", sumLeft = " << sumLeft << std::endl;
if (tmpSum == 0) return i;
if (tmpSum < 0) i++;
else return -1;
}
return -1;
}
int main(void)
{
//int arr[] = { 7, 0, 2, 6, 3 }; // Splittable at index 2, elem 2
//int arr[] = { 7, 0, 2, 6, 3, 18 }; // Splittable at index 4, elem 3
//int arr[] = { -7, 0, 2, 6, 3, 11 }; // Not splittable
//int arr[] = { -7, 0, 2, 6, -14, 3 }; // Splittable at index 2, elem 2
int arr[] = { -7, 0, 2, 6, 2, 3 }; // Splittable at index 4, elem 2
const int size = sizeof(arr)/sizeof(int);
PRINT(arr, size);
int at = isSplittable(arr, size);
if (at > 0)
std::cout << "The array is splittable at " << at << " (ie, at element " << arr[at] << ")" << std::endl;
else
std::cout << "The array is NOT splittable" << std::endl;
return 0;
}
In Java, unless I'm missing something (O(n) time, O(1) memory)
boolean isSplittable(int [] arr) {
if ( (arr==null) || (arr.length<=1) ) return false;
int total = 0;
for (int i=0; i<arr.length; i++) total += arr[i];
if (total%2==1) return false;
int half = total/2;
total = 0;
for (int i=0; i<=arr.length; i++) {
total += arr[i];
if (total==half) return true;
}
return false;
}
It can be done as follows:
// Take two int(s) for the sum as leftSum & rightSum.
int start = 0, end = n-1;
int leftSum = data[start];
int rightSum = data[end];
while ( start < end )
{
If ( leftSum > rightSum )
{
rightSum += data[--end];
}
else
{
leftSum += data[++start];
}
}
if(leftSum == rightSum)
{
return true;
}
return false;
First lets prove that an array can be split at only one point:
- puneet.sohi March 28, 2014E.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