Skip to content

Instantly share code, notes, and snippets.

@parshap
Created December 18, 2013 09:19
Show Gist options
  • Save parshap/8019520 to your computer and use it in GitHub Desktop.
Save parshap/8019520 to your computer and use it in GitHub Desktop.
Find pivot index
// Return the "pivot index" of the given array of numbers. The pivot index is
// the index where the sum of the numbers on the left is equal to the sum of
// the numbers on the right.
function pivot(numbers) {
validateInput(numbers);
// Find a pivot index by testing each index
for (var i = 0; i < numbers.length; i++) {
var leftSum = sum(numbers.slice(0, i));
var rightSum = sum(numbers.slice(i + 1));
if (leftSum === rightSum) {
return i;
}
}
// No pivot found
return -1;
}
// More efficient, less readable version of pivot()
function pivotEfficient(numbers) {
validateInput(numbers);
// Keep track of running sums as we iterate array
var leftSum = 0, rightSum = sum(numbers);
for (var i = 0; i < numbers.length; i++) {
rightSum -= numbers[i];
if (leftSum === rightSum) {
return i;
}
leftSum += numbers[i];
}
// No pivot found
return -1;
}
// Check validity of pivot() input and throw helpful error if not valid
function validateInput(numbers) {
// Must be array
if ( ! Array.isArray(numbers)) {
throw new Error("Argument must be an array");
}
// Must be all numbers
if ( ! numbers.every(isNumber)) {
throw new Error("Every array element must be a number");
}
}
// Return the sum of the numbers in the given array
function sum(numbers) {
return numbers.reduce(function(acc, current) {
return acc + current;
}, 0);
}
// Determine if the given input is a number
function isNumber(number) {
return typeof number === "number";
}
// Test pivot() implementation
function test() {
var assert = require("assert");
// Bad input
[
undefined,
null,
0,
10,
-10,
Infinity,
"foo",
[1, "foo", 2]
].forEach(function(arg) {
var thrown = false;
try {
pivot(arg);
}
catch (e) {
thrown = true;
}
assert(thrown);
});
// Reference case
assert(pivot([1, 4, 6, 3, 2]) === 2);
// No valid pivot
assert(pivot([]) === -1);
assert(pivot([1, 2, 3]) === -1);
// Multiple pivots
assert(pivot([1, 2, 0, 0, 3]) === 2);
// Other cases
assert(pivot([1]) === 0);
assert(pivot([1, 0]) === 0);
assert(pivot([0, 1]) === 1);
assert(pivot([1, 1, 1]) === 1);
assert(pivot([8, 1, 5, 4, 3, 2]) === 2);
// Negatives numbers
assert(pivot([5, -1, 100, 6, -2]) === 2);
assert(pivot([-8, 5, -3, -5]) === 1);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment