Splitting array into equal halves-CodePudding

Problem: find an index N where the sum of the integers to the left of N is equal to the sum of the integers to the right of N. If there is no index that would make this happen, return -1.

My solution

function findEvenIndex(arr) {
  var sum = i => i.reduce((a, b) => a   b),
    l = arr.length;

  for (let j = 0; j <= l; j  ) {
    if (sum(arr.slice(0, j - 1)) === sum(arr.slice(j, l))) {
      return j
    } else {
      continue;
    }
  }
  return -1

}
console.log(
  findEvenIndex([1, 2, 3, 4, 3, 2, 1])
)

When I run this on say findEvenIndex([1,2,3,4,3,2,1]), It doesn't return anything? Where is the error that prevents 3 from being returned in the case of this example?

I've set the for loop procedure as follows to see what's going on

  for(let j = 0; j <= arr.length; j  ){
    var left = arr.slice(0, j-1), right = arr.slice(j)
    console.log(left, right)
  } 
/* returns 
[1] [3,4,3,2,1] 
[1,2] [4,3,2,1] 
[1,2,3] [3,2,1]
as expected
*/

However, when try to console.log the sum of these arrays:

function sum(i){ return i.reduce((a, b) => a b)} 
    
    var l = arr.length;
  
  for(let j = 0; j <= l; j  ){
    var left = arr.slice(0, j-1), right = arr.slice(j)
    console.log(sum(left), sum(right))
  }

Using the snippet above, findEvenIndex([1,2,3,4,3,2,1]) returns "15 16"?

CodePudding user response：

You can get the index like following using reduce(). Your implementation regarding reduce() is not correct.

function findEvenIndex(arr)
{
  for(let i = 0; i < arr.length; i  ) {
    let leftSum = arr.slice(0, i).reduce((accumulator, current) => accumulator   current, 0);
    let rightSum = arr.slice(i   1).reduce((accumulator, current) => accumulator   current, 0);
    if (leftSum === rightSum) {
      return i;
    }
  }
  return -1;
}
console.log(
  findEvenIndex([1, 2, 3, 4, 3, 2, 1])
)

Please check following blog to find out how Array reduce() work

https://www.javascripttutorial.net/javascript-array-reduce/

CodePudding user response：

The main issue with your code is that calling sum([]) throws an error (which you will find in the console during debugging):

Reduce of empty array with no initial value

The reduce method does not know what to return if your array doesn't have any values. You solve it by passing the initial value as a second argument to .reduce:

const add = (a, b) => a   b;

[1, 2, 3].reduce(add); // add(add(1, 2), 3)
[1, 2].reduce(add);    // add(1, 2)
[1].reduce(add);       // 1
[].reduce(add);        // ERROR: Reduce of empty array 
                       //        with no initial value

[1, 2].reduce(add, 0); // add(add(0, 1), 2)
[1].reduce(add, 0);    // add(0, 1)
[].reduce(add, 0);     // 0

Once you fix that, it's easier to debug the rest of the code.

Fixing it

Here's an example that I think does what it should do:

Show code snippet

function findEvenIndex(arr) {
  //                    Add a seed value --v
  var sum = i => i.reduce((a, b) => a   b, 0),
      l = arr.length;

  for (let j = 0; j <= l; j  ) {
    const left = arr.slice(0, j);
    const right = arr.slice(j   1);
    const leftSum = sum(left);
    const rightSum = sum(right);
    
    console.log(
      { left, right, leftSum, rightSum }
    );
    
    if (leftSum === rightSum) {
      return j
    }
  }
  return -1
}

console.log(
  findEvenIndex([1]), // 0
  findEvenIndex([1, 2, 3, 4, 3, 2, 1]), // 3
  findEvenIndex([10, 0, 5, 5]), // 1
  findEvenIndex([3, 2, 1]) // -1
)

Another approach

Note that looping over all elements of the array for every index is quite expensive! A more efficient approach would be:

Take the sum of the source array, store it as rightSum
Define leftSum as 0
Look at the integer value at index 0 and subtract it from rightSum
If leftSum === rightSum, return 0
Else, add value to leftSum and increment index
Once you've reached the final index, return -1

Show code snippet

const findEvenIndex = (arr) => {
  let leftSum = 0;
  let rightSum = arr
    .reduce((a, b) => a   b, 0);
  
  for (let i = 0; i < arr.length; i  = 1) {
    const n = arr[i];
    rightSum -= n;
    
    if (leftSum === rightSum) return i;
    leftSum  = n;
  }

  return -1;
}

console.log(
  findEvenIndex([1]), // 0
  findEvenIndex([1, 2, 3, 4, 3, 2, 1]), // 3
  findEvenIndex([10, 0, 5, 5]), // 1
  findEvenIndex([3, 2, 1]) // -1
)

CodePudding user response：

Upon finishing my solution, I noticed that it's effectively the same as @Abu's answer above. The idea is to brute force the way through the array, comparing the two halves as you go.

/* 
    Find an index N where the sum of the integers to the left of N is equal to the sum of the integers to the right of N. If there is no index that would make this happen, return -1
*/

const array = [10, 90, 10, 1, 10, 90, 10];

// incrementTotal :: (Number t, Number n) -> t
incrementTotal = (total, number) => total   number;

// indexIsEqual :: (Array a, Number c) -> Boolean
function indexIsEqual(array, count) {
    let chunkL = array.slice(0, count-1);
    let chunkR = array.slice(count , );

    return chunkL.reduce(incrementTotal) === chunkR.reduce(incrementTotal); 
}

// findEvenIndex :: (Array a) -> (a[x] || -1)
function findEvenIndex(array) {
    for (let count = 2; count < array.length; count  ) {
        if (indexIsEqual(array, count)) {
            return array[count-1];
        }
    }
    return -1;
}

console.log(findEvenIndex(array));