Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Least Common Multiple of an array values using Euclidean Algorithm

I want to calculate the least common multiple of an array of values, using Euclideans algorithm

I am using this pseudocode implementation: found on wikipedia

function gcd(a, b)
    while b ≠ 0
       t := b; 
       b := a mod b; 
       a := t; 
    return a;

My javascript implementation is such

function smallestCommons(arr) {

  var gcm = arr.reduce(function(a,b){

    let minNum = Math.min(a,b);
    let maxNum = Math.max(a,b);
    var placeHolder = 0;

    while(minNum!==0){
        placeHolder = maxNum;
        maxNum = minNum;
        minNum = placeHolder%minNum;
    } 

    return (a*b)/(minNum);
  },1);

  return gcm;
}


smallestCommons([1,2,3,4,5]);

I get error, on my whileloop

Infinite loop

EDIT Some corrections were made, at the end of gcm function, I used 0 as the initial start value, it should be 1, since you can't have a gcm from 0.

EDIT2 The expected output should be 60, since thats the least common multiple of 1,2,3,4,5

like image 768
Vincent Tang Avatar asked Nov 27 '22 13:11

Vincent Tang


2 Answers

With ES6

const gcd = (a, b) => a ? gcd(b % a, a) : b;

const lcm = (a, b) => a * b / gcd(a, b);

Then use reduce on given array of integers:

[1, 2, 3, 4, 5].reduce(lcm); // Returns 60

With ES5

var gcd = function (a, b) {
    return a ? gcd(b % a, a) : b;
}

var lcm = function (a, b) {
    return a * b / gcd(a, b);
}

Then use reduce on given array of integers:

[1, 2, 3, 4, 5].reduce(lcm); // Returns 60
like image 158
Елин Й. Avatar answered Nov 30 '22 02:11

Елин Й.


Did you intentionally tangle all variables and operator sequence? ;-)

  while(minNum!==0){
        placeHolder = minNum;
        minNum = maxNum % minNum;
        maxNum = placeHolder;
    } 

    //here maxNum = GCD(a,b)

    return (a*b) / (maxNum);  //LCM
like image 44
MBo Avatar answered Nov 30 '22 03:11

MBo