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):

1
2
3
4
5

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):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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):

1
2
3
4
5
6
7
8

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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));
      }
     }
}