Get the gcd of n numbers

Question

This could seem an easy question but I cannot find a solution. I must find the gcd of n numbers.

public int getGCD(int a, int b) {
 if (b == 0) { return a; }
 else { return getGCD(b, a%b); }
}

This is the popular recursive way that calculates the gcd of two numbers. But if I need to get the gcd of 3, 4, 5... n numbers? I was thinking to do something like this:

public int getGCD(int[] a) {
 //the code  
}

There is an array of integer as parameter, but I have no idea about the code. Do you have any suggestion?

Answer 1

The GCD of a multiple numbers gcd( n1, n2, .... nx ) can be computed by incrementally computing the GCD of two numbers:

gcd( n1, n2, .... nx ) == gcd( n1, gcd( n2, gcd( ... , nx ) ) )

Every divisor for all numbers, has to be a divisor for any subset of these numbers. Which in turn leads to the above formula.

By reusing your given getGCD(int, int) function for two numbers, we can create an additional overload that takes a list of one or more numbers:

public int getGCD(int a, int b) {
 // implementation for two numbers goes here
}

public int getGCD(int[] a) {
  // the GCD of a number with itself is... itself
  int gcd = a[0];

  // compute incrementally
  for( int i=1; i<a.length; i++ ) {
    gcd = getGCD( gcd, a[i] );
  }

  // return result
  return gcd;    
}