Alberto Miola - 2 years ago 79
Java Question

# Get the gcd of n numbers

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?

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;
}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download