Daily Challenge #265 - Equal Sides

#challenge

dev.to staff Jul 7, 2020 ・2 min read

You are going to be given an array of integers. Your job is to take that array and 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.

For example:

Let's say you are given the array {1,2,3,4,3,2,1}: Your function will return the index 3, because at the 3rd position of the array, the sum of left side of the index ({1,2,3}) and the sum of the right side of the index ({3,2,1}) both equal 6.

Let's look at another one.
You are given the array {1,100,50,-51,1,1}: Your function will return the index 1, because at the 1st position of the array, the sum of left side of the index ({1}) and the sum of the right side of the index ({50,-51,1,1}) both equal 1.

Input:
An integer array of length 0 < arr < 1000. The numbers in the array can be any integer positive or negative.

Output:
The lowest index N where the side to the left of N is equal to the side to the right of N. If you do not find an index that fits these rules, then you will return -1.

Note:
If you are given an array with multiple answers, return the lowest correct index.

Tests

{1,2,3,4,3,2,1}
{1,100,50,-51,1,1}
{20,10,30,10,10,15,35}
{-8505, -5130, 1926, -9026}

Good luck!

This challenge comes from Shivo on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

Discussion (11)

SavagePixie • Jul 7 '20 • Edited

JavaScript

const sum = (a, b) => a + b

const doStuff = xs => xs.findIndex(
  (x, i, arr) => arr.slice(0, i).reduce(sum) === arr.slice(i + 1).reduce(sum)
)

Edison Pebojot(👨‍💻) • Jul 8 '20 • Edited

This code is clever, however, when we talk about best performance with $O\lparen n \rparen$ , this code is slower. See the JsPerf Performance of your code here: pancake-island-lollipop. You can try this instead:

// Shorthand notation
let answer=(a,b=a=>a.reduce((a,b)=>a+b,0))=>a.findIndex((_,i)=>b(a.slice(0,i))==b(a.slice(i+1)))

Currently, the fastest form of loop is a standard for loop with length caching

for (var i = 0, len = myArray.length; i < len; i++)

This code also solves the problem with length caching, in my opinion, this is also the fastest in general:

Miguel Manjarres • Jul 7 '20

Python

from functools import reduce

def findIndex(arr):
    sum = lambda a, b : a + b
    for i in range(len(arr)):
        leftSum = reduce(sum, arr[0:i+1])
        rightSum = reduce(sum, arr[i:len(arr)])
        if leftSum == rightSum:
            return i
    return -1

print(findIndex([1,2,3,4,3,2,1])) # 3
print(findIndex([1,100,50,-51,1,1])) # 1
print(findIndex([20,10,30,10,10,15,3])) # -1
print(findIndex([-8505, -5130, 1926, -9026])) # -1

heykieran • Jul 8 '20

Clojure

(defn equal-sides
  [candidate-array]
  (loop
   [c candidate-array idx 1 lt 0 rt 0]
    (cond
      (empty? c) -1
      (and (= lt rt) (= 1 (count c))) idx
      :else
      (let
       [inc-l (> (+ rt (last c)) (+ lt (first c)))]
        (recur
         (if inc-l (rest c) (butlast c))
         (if inc-l (inc idx) idx)
         (+ lt (if inc-l (first c) 0))
         (+ rt (if-not inc-l (last c) 0)))))))

Dimitri Lahaye • Jul 8 '20

My humble solution:

function findN(array) {
  reducer = (s, o) => s + o;
  return array.findIndex((a, i, arr) => arr.slice(0, i).reduce(reducer, 0) === arr.slice(i + 1 - array.length).reduce(reducer, 0));
}

E. Choroba • Jul 8 '20

Perl

#!/usr/bin/perl
use strict;
use warnings;
use experimental qw{ signatures };
use List::Util qw{ sum };

sub equal_sides ($arr) {
    my ($left, $current, $right) = (0, 0, sum(@$arr[1 .. $#$arr]));
    until ($current > $#$arr || $left == $right) {
        $left += $arr->[$current];
        $right -= $arr->[++$current] // 0;
    }
    return $current > $#$arr ? -1 : $current
}

use Test::More tests => 4;

my @tests = ([1, 2, 3, 4, 3, 2, 1],        3,
             [1, 100, 50, -51, 1, 1],      1,
             [20, 10, 30, 10, 10, 15, 35], 3,
             [-8505, -5130, 1926, -9026], -1);

while (my ($arr, $result) = splice @tests, 0, 2) {
    is equal_sides($arr), $result;
}

Mofid Jobakji • Jul 8 '20

javascript

 const  fn = (arr) => {
  let sum = 0;
  const total = arr.reduce((a,b)=> a+b , 0);
  return arr.findIndex((x, i, arr) => (total - (sum += x)) * 2 + x === total) ;
}

console.log(fn([1, 2, 3, 4, 3, 2, 1])); // 3
console.log(fn([1, 100, 50, -51, 1, 1])); // 1
console.log(fn([20, 10, 30, 10, 10, 15, 35])); // 3
console.log(fn([-8505, -5130, 1926, -9026]));// -1
console.log(fn([11,4,30,5,10,20,15]));// 3

Hayden Mankin • Jul 7 '20

Javascript

const equalSides = (arr) => {
  let right = arr.reduce((a, b) => a + b);
  let left = 0;
  return arr.findIndex(i => {
    right -= i;
    if (left == right) {
      return true;
    }
    left += i;
    return false;
  });
};

console.log(equalSides([1, 2, 3, 4, 3, 2, 1])); // 3
console.log(equalSides([1, 100 , 50, -51 , 1 , 1])); // 1
console.log(equalSides([20, 10, 30, 10, 10, 15, 35])); // 3
console.log(equalSides([-8505, -5130, 1926, -9026])); // -1

Amin • Jul 8 '20

Haskell

halve :: [a] -> ([a], [a])
halve list =
    (take half list, drop (half + rest) list)

    where
        size = length list
        half = div size 2
        rest = mod size 2


isEqualSides :: [Int] -> Int
isEqualSides []        = -1
isEqualSides integers  =
    if (sum firstHalf) == (sum secondHalf) then 
        length firstHalf

    else
        isEqualSides (init firstHalf ++ tail secondHalf)

    where
        (firstHalf, secondHalf) = halve integers