GCD/LCM

node v0.12.18
version: 1.0.0
endpointsharetweet
A recursive gcd function for a 2-length array
function findGcd(arr){ if (arr[1] == 0){ return arr[0]; } else { return findGcd([arr[1], arr[0] % arr[1]]); } } findGcd([210, 45]);
Using above for finding LCM of an arbitrary length array
function findBigLCM(arr){ if (arr.length === 2){ return arr[0] * arr[1] / findGcd([arr[0], arr[1]]); } else { // arr.length > 2 var pairGcd = findGcd([arr[0], arr[1]]); var pairLCM = arr[0] * arr[1]/pairGcd; var remaining = arr.slice(2); remaining.unshift(pairLCM); //recurse! return findBigLCM(remaining); } } findBigLCM([1, 2, 3, 4, 5]);
Two tips from free code camp help board: 1) slice extracts/make a copy (keep original unmodified); splice extracts (modify the original ) 2) pretty sure you just want to reduce function GCD(a,b) { return ... } function LCM(a,b) { return a * b / GCD(a, b); } lcm = arr.reduce(LCM);
So, let's try those. First, modify the above to use splice instead of slice (though slice is more stateless, so what I'm going for eventually...)
function findBigLCM(arr){ if (arr.length === 2){ return arr[0] * arr[1] / findGcd([arr[0], arr[1]]); } else { // arr.length > 2 var pairGcd = findGcd([arr[0], arr[1]]); var pairLCM = arr[0] * arr[1]/pairGcd; //var remaining = arr.slice(2); arr.splice(2).unshift(pairLCM); //recurse! return findBigLCM(remaining); } } findBigLCM([1, 2, 3, 4, 5]);
Woot - so that eliminates a line. Try without pairLCM and pairGcd variables (though that makes it harder to read)
function findBigLCM(arr){ if (arr.length === 2){ return arr[0] * arr[1] / findGcd([arr[0], arr[1]]); } else { // arr.length > 2 // replace first 2 values of array with their LCM arr.splice(2).unshift(arr[0] * arr[1]/(findGcd([arr[0], arr[1]]))); //recurse! return findBigLCM(remaining); } } findBigLCM([1, 2, 3, 4, 5]);
So tip 1 helps. Let's try the reduce approach.
function LCM(a,b) { return a * b / findGcd(a, b); } lcm = ([1, 2, 3, 4, 5]).reduce(LCM); console.log(lcm);
This doesn't seem to work.
Loading…

no comments

    sign in to comment