Calculating the sum of array elements to the left and right

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>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!!

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.

StackExchange Code Review Q#101181, answer score: 3