How can I find the GCD of two or more integers, javascript? No methods

Viewed 187

I already know how to find the GCD with no methods (below), but how can I create a function that will do it with either two or more integers?

function greatest(x,y){
  return x<0 || y<0 ? null : x%y===0 ? y : greatest(y, x%y);
}
console.log(greatest(64,2)); //2
console.log(greatest(88,200)); //8

//Finding the gcd of two integers using recursion 
 const gcd = function(x, y) {
  if (!y){ //if y is zero return back x
    return x;
  }
  return gcd(y, x % y);
}
5 Answers

You can use the spread syntax to group remaining arguments in an array and take the GCD one pair at a time. The LCM can be done very similarly by a similar recursion.

const gcd = function(x, y, ...z) {
  if (!y && z.length > 0) {
    return gcd(x, ...z);
  }
  if (!y) {
    return x;
  }
  return gcd(y, x % y, ...z);
}

console.log(gcd(6, 12, 8));
console.log(gcd(9, 15, 36));

Edit: Here's LCM, as requested in the comments. Note that you need to divide multiple GCDs, you cannot group multiple GCDs together and divide.

const lcm = function(x, y, ...z) {
  if (z.length == 0) {
    return x * y / gcd(x, y);
  }
  return lcm(x * y / gcd(x, y), ...z);
}

This version uses a standard recursive binary gcd version, and then creates a gcdAll which recurs on the list of numbers supplied, bottoming out with a call to gcd:

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

const gcdAll = (n, ...ns) =>
  ns.length == 0 ? n : gcd (n, gcdAll (...ns))

console .log (gcdAll (1100, 495, 165)) //=> 55

I find this conceptually simple and easy to understand. But I am also intrigued by the answer from Exalted Toast, which shuffles parameters in a really useful manner.

This question needs a mix of recurstion and the spread operator (in function parameters):

//Finding the gcd of two integers using recursion 
 const gcd = function(x, y) {
  if (!y){ //if y is zero return back x
    return x;
  }
  return gcd(y, x % y);
}

function gcdOfMultipleNumbers(...args) {
  var newArr = args.filter(a => Number.isInteger(a) && a !== 0) // remove decimals and zeros
  if(newArr.length <= 0) return 0; // if no arguments remain after filtering
  if(newArr.length === 1) return newArr[0]; // if one argument remains after filtering
  if(newArr.length === 2) return gcd(...newArr); // if two arguments remain after filtering
  // if there are more than two arguments which remain
  return gcdOfMultipleNumbers(gcd(newArr.shift(), newArr.shift()), ...newArr)
}

console.log(gcd(64,2)); //2
console.log(gcd(88,200)); //8

console.log(gcdOfMultipleNumbers(64, 24, 4, 32)); // 4
console.log(gcdOfMultipleNumbers(88, 200, 44)); //4

This question reminded me of my college life. It was asked by our Professor. So, the actual math behind the scene is: gcd(a, b, c) = gcd(a, gcd(b, c))=gcd(gcd(a, b), c)... . The function you can write is here:

// the recursive function: gcd
function gcd(num1, num2) {
    // base case
    if (num1 === 0) {
        return num2
    }

    return gcd(num2 % num1, num1);
}

function multiNumGCD(...args) {
    let len = args.length;
    let res = args[0];
    for (let i = 1; i < len; i++) {
        res = gcd(args[i], res);
        return res;
    }
}

console.log(multiNumGCD(3, 6, 7));

Hope you find it useful !!!

Here is something that worked for me

function gcd(arr) {
let numCheck = true 
arr.forEach(n => {
if(isNaN(n)) numCheck = false
})
if(!numCheck) return null;
let nums = arr.map(n => parseInt(n));
if(nums.some(n => n < 1)) return null;
let lowestNum;
nums.forEach(n => {
if(lowestNum === undefined || n < lowestNum) {
lowestNum = n;
}
})
let gcd;
for(let i = 0; i <= lowestNum; i++) {
let test = nums.filter(n => !(n%i))

if(test.length !== nums.length) {null} else {
gcd = i
}
}
return gcd;
}

And to execute it, do this:

gcd([6, 9, 12]) //3
//it also works with strings
gcd(['6', '9', '12']) //3

P.S. idk for sure but by gcd you mean greatest common divisor, right?

Related