loading...

Daily Challenge #265 - Equal Sides

thepracticaldev profile image dev.to staff ・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

pic
Editor guide
Collapse
savagepixie profile image
SavagePixie

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)
)
Collapse
edisonnpebojot profile image
Edison Pebojot(👨‍💻)

This code is clever, however, when we talk about best performance with O(n)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)))
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))) console.log(answer([1, 2, 3, 4, 3, 2, 1])); // prints '3' console.log(answer([1, 100, 50, -51, 1, 1])); // prints '1' console.log(answer([20, 10, 30, 10, 10, 15, 35])); // prints '3' console.log(answer([-8505, -5130, 1926, -9026])); // prints '-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:

function answer(arr) { var left = 0, right = arr.reduce((p, c) => p + c, 0) for (var i = 0, len=arr.length; i < len; i++) { if (i > 0) left += arr[i - 1]; right -= arr[i]; if (left == right) return i; } return -1; } console.log(answer([1, 2, 3, 4, 3, 2, 1])); // prints '3' console.log(answer([1, 100, 50, -51, 1, 1])); // prints '1' console.log(answer([20, 10, 30, 10, 10, 15, 35])); // prints '3' console.log(answer([-8505, -5130, 1926, -9026])); // prints '-1'
Collapse
devtony101 profile image
Miguel Manjarres

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
Collapse
heykieran profile image
heykieran

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)))))))
Collapse
dimitrilahaye profile image
Dimitri Lahaye

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));
}
Collapse
choroba profile image
E. Choroba

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;
}
Collapse
moufeed_m profile image
Mofid Jobakji

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
Collapse
dry profile image
Hayden Mankin

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
Collapse
aminnairi profile image
Amin

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
Collapse
bracikaa profile image