Calculating the sum of array elements to the left and right

Question

I am using C++ to code the following logic:

An Array is given we have to traverse the array such that sum of array elements to its left must be equal to sum of elements to its right.

BTW this is hackerrank Problem.

Here's the code , but this is giving me time-out, that is my code is too slow for very large input, I want to make it faster.

int sumArray(int arr[],int start,int end){
    int sum = 0;
    for(int i=start;i<=end;i++)
        sum += arr[i];
    return sum;
}

// this is inside main
int ar[N];
    for(int n=0;n<N;n++)
        cin>>ar[n];

    bool found = false;
    if(N == 1)
        found = true;
    for(int i=1;i<N;i++){
        int left = sumArray(ar,0,i-1);
        int right = sumArray(ar,i+1,N-1);
        if( left == right)
            found = true;     
    }
    if (found)
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;

This is how the problem works, this is given array 1 2 3

1 2 3 3

In the first test case, no such index exists.

In the second test case, A[0] + A[1] = A[3]. So 2(start from 0) is the position where this condition occurs.

this is slow for N=10000 elements in array it excceds 2ms time limit

So where should my code be improved? My mind says I should give a try with dynamic programming because I am calling same process each time and start it from zero. Is there any good method to do this. Or is there a better way to make above code work for large inputs (I know there's some better way)?

All suggestions are warmly welcomed!!

Answer 1

This problem is a common problem in coding challenges, and it's a nice one, because there's a really elegant solution which is really fast. It does not even need dynamic programming.... just a little trick of logic.

Your solution takes each position, and for each position, sums all values to the left, and right, then it repeats that until it hits a match. Your solution thus scans all N elements about N/2 times (on average, you scan half the data until you hit a match). This makes your solution a time-complexity of \$O(n^2)\$. If you double the size of the input, the solution takes 4 times longer.

Now, a simple solution is to scan the entire data once, and calculate the sum of all the values:

int sum = 0;
for(int i = 0; i < N; i++){
    sum += arr[i];
}

Note, in the code above, I have added spaces to the expressions to make them more readable.

Now, with that value, if your position is 0, the sum to the left is 0, and to the right is sum.

If you move your cursor to the right, the sum to the left is now the value at element 0 ar[0], and to the right is the sum - ar[0].

So, you can loop until you find the match.....

int left = 0;
int right = sum;
for(int i = 0; i < N; i++){
    left += arr[i];
    right -= arr[i];
    if (left == right) {
        return i;
    }
}

See how, as you go, you can "shift" the value from the one side to the other? This makes the solution a simple \$O(n)\$ complexity.

Answer 2

You don't need to add up the array before processing. (per vnp's comment)

Process the numbers from both ends, with the sum determining which end to take next.

Special conditions:

• Less than 3 elements? => fail?
• Is a single number success or fail?
• What if only two numbers? where one is zero? both zero?

Algorithm:

initialize left index to -1 and right index to size of array, sum to zero.

loop:
  if the left and right index are separated by 2 (with one index in the middle),
     if the sum is 0, the middle index is the result, if not 0, then no solution.
  If the sum is zero or positive, subtract the next element on the left.
  else (is negative), add the next element from the right.

Is zero is a valid element? If so, then there could be multiple solutions. e.g. array 1 2 0 0 0 1 2 , index 2, 3, 4 are all solutions.

This method also avoids exceeding the max value for sum. If the array size is arbitrary, then there can always be a situation where adding all the elements can exceed the data type of sum. For this method, sum data type needs to be able to hold twice one array element.

Answer 3

My proposal is only marginally different from @rolfl's, but I feel like advertising a more modern C++ style:

#include <iostream>
#include <algorithm>

int main() {
    int array[] = {1,2,3,-2,-2, 4,1,2,-4,3,4};
    // make each element the sum of the elements to its left
    auto first = std::begin(array), previous = first, last = std::end(array);
    std::for_each(std::next(first), last, [&previous](auto& current) { current += *previous++; });
    // then look for half the last element
    bool divisible = std::find(first, last, *std::rbegin(array)/2) != last;
    std::cout << (divisible ? "YES" : "NO");
}

I also believe this approach is a bit more flexible. For instance, if you know there aren't negative numbers in the array, then you also know the array is sorted and can leverage the faster binary search with only minimal change.