The challenge
Find the greatest common divisor of two positive integers. The integers can be large, so you need to find a clever solution.
The inputs x and y are always greater or equal to 1, so the greatest common divisor will always be an integer that is also greater or equal to 1.
The solution in Java code
Option 1 (using Euclidean Algorithm):
public class GCD {
public static int compute(int x, int y) {
return (x % y != 0) ? compute(y, x % y) : y;
}
}
Option 2 (using a loop):
public class GCD {
public static int compute(int x, int y) {
int gcd = 0;
for(int i=1; i<= x && i<= y; i++){
if(x %i == 0 && y %i ==0){
gcd = i;
}
}
return gcd;
}
}
Option 3 (using BigInteger):
import static java.math.BigInteger.valueOf;
import java.math.BigInteger;
public class GCD {
public static int compute(int x, int y) {
return valueOf(x).gcd(valueOf(y)).intValue();
}
}
Test cases to validate our solution
import org.junit.Test;
import static org.junit.Assert.assertEquals;
import org.junit.runners.JUnit4;
public class GreatestCommonDivisorTest {
@Test
public void testGcd() {
assertEquals(6, GCD.compute(30,12));
assertEquals(1, GCD.compute(8,9));
assertEquals(1, GCD.compute(1,1));
}
@Test
public void testSomeLargerValues() {
for (int i=0;i<20;i++){
int x = randint(10000,100000);
int y = randint(100,1000);
int ans=my_gcd(x,y);
int x2 = randint(10000,100000);
int ans2=my_gcd(x2*y,x*y);
assertEquals("Testing GCD.compute("+ x +","+ y +")== "+ ans, ans, GCD.compute(x,y));
assertEquals("Testing GCD.compute("+ x2*y +","+ x*y +")== "+ ans2, ans2, GCD.compute(x2*y,x*y));
}
}
}
