Created
December 18, 2013 09:19
-
-
Save parshap/8019520 to your computer and use it in GitHub Desktop.
Find pivot index
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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