Split, Sum and Iterate through an Integer Array Until Each Side is Equivalent (Javascript)

Question

Title: Determine Equal Sides Of An Array

Question:

I need help writing a JS function that sums the left and right integers on either side of an incrementing index until it returns the index and integer where the left and right integer sums are equivalent.

Abstract Example:

Note: "|x|" is the indexed integer that separates the left and right integer sums.

//ignore "|x|" when adding each side, and Sum both "Left|x|Right" sides until the Right and Left side are determined "===" (eg.equivalent)

SUM   LEFT <|x|> RIGHT   SUM   CHECK
1  = [|1|2,3,4,3,2,1 ] = 15  //!==
1  = [ 1|2|3,4,3,2,1 ] = 13  //!==
3  = [ 1,2|3|4,3,2,1 ] = 10  //!==
6  = [ 1,2,3|4|3,2,1 ] = 6   //===
10 = [ 1,2,3,4|3|2,1 ] = 3   //!==
13 = [ 1,2,3,4,3|2|1 ] = 1   //!==
15 = [ 1,2,3,4,3,2|1|] = 1   //!==

Answer:

In this example, index 3 on integer 4 splits the array where both the left and right side sums are equivalent.

Return:

When the function determines that both the left and right sides are equivalent, it should return the indexed integer (eg. 4). If neither side is equivalent during all iterations, then it should return -1.

Thank you!

Answer 1

The solution you have come up with works, however it could be very inefficient with larger arrays.

Instead, consider an approach where you keep a running total so that you're not constantly re-adding entire sections of the array.

function findEvenIndex(arr) {
  let left = 0;
  // get the total of all numbers once
  let right = arr.reduce((a,b)=>a+b, 0);
  for( let i=0; i<arr.length; i++) {
    right -= arr[i];
    if( left === right) return i;
    left += arr[i];
  }
  return -1;
}
console.log(findEvenIndex([1,2,3,4,3,2,1]));

Here is a timed comparison of your solution and mine:

function findEvenIndex1(arr)
{
  function sum(arr){
    return arr.reduce(function(a,b){return a+b;},0);
  }

  return arr.findIndex(function(el,i,arr){
    return sum(arr.slice(0, i)) === sum(arr.slice(i+1,arr.length));
  });
}
function findEvenIndex2(arr) {
  let left = 0;
  // get the total of all numbers once
  let right = arr.reduce((a,b)=>a+b, 0);
  for( let i=0; i<arr.length; i++) {
    right -= arr[i];
    if( left === right) return i;
    left += arr[i];
  }
  return -1;
}

console.time("yours-small");
console.log(findEvenIndex1([1,2,3,4,3,2,1]));
console.timeEnd("yours-small");
console.time("mine-small");
console.log(findEvenIndex1([1,2,3,4,3,2,1]));
console.timeEnd("mine-small");

let huge = Array.from({length:10000},(_,i)=>i+1);
huge = huge.concat(huge.slice(0,huge.length-1).reverse());
console.time("yours-big");
console.log(findEvenIndex1(huge));
console.timeEnd("yours-big");
console.time("mine-big");
console.log(findEvenIndex2(huge));
console.timeEnd("mine-big");

Even with a very small array of just 7 items, my solution is an order of magnitude faster, and with the larger array mine is 400 times faster!