Find the Greatest Common Divisor in Java

1 min read 238 words

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));
      }
     }
}
Tags:
Andrew
Andrew

Andrew is a visionary software engineer and DevOps expert with a proven track record of delivering cutting-edge solutions that drive innovation at Ataiva.com. As a leader on numerous high-profile projects, Andrew brings his exceptional technical expertise and collaborative leadership skills to the table, fostering a culture of agility and excellence within the team. With a passion for architecting scalable systems, automating workflows, and empowering teams, Andrew is a sought-after authority in the field of software development and DevOps.

Tags