CODEWITHSUNDEEP
javascriptmath
Тома Томов
Тома Томов

Reputation: 51

GCD of more than 2 numbers

function gcd (a, b) {
    if(b == 0){
        return a;
    }
    return gcd(b, a%b);
}

function gcd_more_than_two_numbers (a) {
    var last = Math.max.apply(null, a);
    var first = Math.min.apply(null, a);    

    return gcd(first, last);
}

console.log(gcd_more_than_two_numbers([9999,213123,9,15,27])); 
console.log(gcd_more_than_two_numbers([5,10,15,25]));

Is it right to take the lowest and the highest values in an array and find a gcd for all the numbers between them ? Is it mathematically right ?

Upvotes: 1

Views: 1370

Answers (4)

Rajesh
Rajesh

Reputation: 24915

You can use array.every as well to check validity:

Sample

function getGCD(arr) {
  var min = Math.min.apply(null, arr);
  var gcd = 1;
  for (var i = gcd + 1; i <= min; i++) {
    if (arr.every(x => x % i === 0))
      gcd = i;
  }
  return gcd;
}
var arr = [100, 13000, 1110];
var arr2 = [9999, 213123, 9, 15, 27]
console.log(getGCD(arr))
console.log(getGCD(arr2))

Upvotes: 1

maioman
maioman

Reputation: 18734

Is it right to take the lowest and the highest values in an array and find a gcd for all the numbers between them ? Is it mathematically right ?

NO.

You need to take the gcd of the first pair and then recalculate against all the other elements of the array, you can do that easily with reduce:

function gcd (a, b) {
    if(b == 0){
        return a;
    }
    return gcd(b, a%b);
}
function gcd_more_than_two_numbers (a) {
  return a.reduce(gcd)
}

console.log(gcd_more_than_two_numbers([9999,213123,9,15,27]))

Upvotes: 6

Vladu Ionut
Vladu Ionut

Reputation: 8193

    function gcd() {
      var arr = Array.prototype.slice.call(arguments);
      return arr.reduce(function(a, b) {
        if (b == 0) {
          return a;
        }
        return gcd(b, a % b);
      });
    }
    console.log(gcd(7,14));
    console.log(gcd(9999,213123,9,15,27)); 
    console.log(gcd(5,10,15,25));

Upvotes: 3

Bathsheba
Bathsheba

Reputation: 234665

No it isn't.

The identity you're after is gcd(a, b, c) = gcd(gcd(a, b), c).

I suggest you unpick the recursion using a loop.

Upvotes: 3

Related Questions