Watson gives Sherlock an array \(A\) of integers. His challenge is to find an element of the array such that the sum of all elements to the left is equal to the sum of all elements to the right. If there are no elements to the left/right, then the sum is considered to be zero. Formally, find an \(i\), such that, \(A_1+A_2+\dots+A_{i-1}=A_{i+1}+A_{i+2}+\dots+A_{n}\)
Example
arr = [5, 6, 8, 11]8 is between two subarrays that sum to 11.
You will be given arrays of integers and must determine whether there is an element that meets the criterion. If there is, return YES. Otherwise, return NO.
Function Description
Complete the balancedSums function in the editor below.
balancedSums has the following parameter(s):
- int arr[n]: an array of integers
Returns
- string: either YES or NO
Input Format
The first line contains \(T\), the number of test cases.
The next \(T\) pairs of lines each represent a test case.
- The first line contains \(n\), the number of elements in the array arr.
- The second line contains \(n\) space-separated integers arr[i] where \(0\leq i<n\).
Constraints
- \(1\leq T\leq 10\)
- \(1\leq n\leq 10^5\)
- \(1\leq arr[i]\leq 2\times 10^4\)
- \(0\leq i<n\)
Solution
From the problem statement it is clear that we are looking for the shift parameter \(i\) to have the sum of the left match the sum of the right. Initially, I thought the array can be rearranged but the problem is much simpler here. We just pile up the total sum of the array and for each element \(i\) of \(A\), we check if
\[\sum\limits_{k=1}^{i} A[k-1] = \sum\limits_{i=1}^N A[i] -\sum\limits_{k=1}^{i} A[k-1] - A[i]\]
Naturally, the implementation then looks like
function balancedSums(arr) {
var totalSum = 0;
var runningSum = 0;
for (var i = 0; i < arr.length; i++) {
totalSum+= arr[i];
}
for (var i = 0; i < arr.length; i++) {
if (runningSum == totalSum - runningSum - arr[i])
return "YES";
runningSum+= arr[i];
}
return "NO";
}As we can rearrange the expression to
\[\sum\limits_{k=1}^{i} A[k - 1] = \sum\limits_{i=1}^N A[i] -\sum\limits_{k=1}^{i} A[N-k]\]
we can simplify the solution to:
function balancedSums(arr) {
var totalSum = 0;
var runningSum = 0;
for (var i = 0; i < arr.length; i++) {
totalSum+= arr[i];
}
for (var i = 0; i < arr.length; i++) {
totalSum-= arr[i];
if (runningSum == totalSum)
return "YES";
runningSum+= arr[i];
}
return "NO";
}