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

• Armaghast: hint: how many times are you computing ar[0]+ar[1]? how many times should it be? Edit: having the full code (what is N?), and some context (I guess it is tested with a software, and that numbers aren't manually entered).
• Ethan Bierlein: As it stands, it's very unclear what you're asking. The post title should be a brief description of what your code does, your post body should explain what the code does in detail, and what you'd like improved. Until these things can be done, I'm voting to close as unclear.
• Suraj Palwe: @Armaghast I know but I haven't studied Dynamic Programming yet. I just started Data structures a week ago. So I am a noob. I searched on internet and found that DP is good to work with these problems
• Armaghast: @SurajPalwe The problem should be simple enough that knowledge in Dynamic Programming isn't needed. Something that works well is to apply your algorithm by hand with a small value of N (like, 5 or 6) on a sheet of paper. Edit: your intuition is right, you are repeated the same action, starting from a 0 index
• Malachi: @EthanBierlein this question is asking how to make the code more efficient to stop it from timing out

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.

• Armaghast: A slightly different solution: replace right by a const int goal = sum / 2, and test if (left == goal)
• rolfl: @Armaghast - interesting solution. It has some technical problems - it may provide "match" results for solutions that have an odd-sum due to the integer division, but an odd-sum can be handled separately. The solution I propose will do an unnecessary full-scan for an odd-sum, your's will fail, though.
• Suraj Palwe: I have updated question, the above code has to make some changes with respect to variable i in the for loop. Thanks for your help
• vnp: While the logic of the solution is correct, the implementation is subject to integer overflow. Notice that we don't need to calculate the sum; working from both ends we only need to keep the imbalance, which is guaranteed to fit an integer.
• Toby Speight: We're in C++, so we can use std::accumulate() instead of writing that for loop.

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.

• JS1: This only works if there are no negative values in the array, which was not part of the problem description.
• greybeard: @JS1: non-negative has not been mentioned in the first four revisions of the question - it has been there in the one equivalent I found on hackerrank. This avoids overflow as far as possible.

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.

• greybeard: You might mention more prominently that this modifies the input.
• Toby Speight: You have presented an alternative solution, but haven't reviewed the code. Please edit it to explain your reasoning (how your solution works and how it improves upon the original) so that everyone can learn from your thought process.