Alberto Miola - 1 year ago 64

Java 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

`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?

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

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**