Contents
raw puzzle

Original Problem

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):

Returns

Input Format

The first line contains \(T\), the number of test cases.

The next \(T\) pairs of lines each represent a test case.

Constraints

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";
}