# GreatestCommonDivisorDemo – Codility – Solution

Java solution to Codility GreatestCommonDivisorDemo problem (PDF) (Lesson 12 – Euclidean algorithm). The problem is to find greatest common divisor between 2 integers using Euclidean algorithm with subtraction and division.

References

Euclidean algorithm tutorial (PDF – Codility)

```
1234567891011121314151617package com.codility.lesson12.euclidean;

public class GreatestCommonDivisorDemo {

//reference: https://codility.com/media/train/10-Gcd.pdf
//find greatest common divisor between 2 integers using Euclidean algorithm with subtraction, division
public int gcdBySubtraction(int A, int B) {
if(A == B) return A;
if(A > B)  return gcdBySubtraction(A-B, B);
else       return gcdBySubtraction(A, B-A);
}

public int gcdByDivision(int A, int B) {
if(A % B == 0) return B;
else           return gcdByDivision(B, A % B);
}
}

```

TestNG test cases for this problem which all passed:

```
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849package test.com.codility.lesson12.euclidean;

import org.testng.Assert;
import org.testng.annotations.BeforeTest;
import org.testng.annotations.DataProvider;
import org.testng.annotations.Test;

import com.codility.lesson12.euclidean.GreatestCommonDivisorDemo;

public class GreatestCommonDivisorDemoTests {
private GreatestCommonDivisorDemo solution;

@BeforeTest
public void setUp() {
solution = new GreatestCommonDivisorDemo();
}

@DataProvider(name = "gcd")
public Object [][] createData1() {
return new Object [][] {
new Object [] { 4, 2, 2  },
new Object [] { 10, 100, 10  },
new Object [] { 25, 35, 5  },
new Object [] { 25, 26, 1  },
new Object [] { 100, 1125, 25  },
};
}

@DataProvider(name = "lcm")
public Object [][] createData2() {
return new Object [][] {
new Object [] { 4, 2, 2  },
new Object [] { 10, 100, 2  },
new Object [] { 25, 35, 5  },
new Object [] { 25, 26, 1  },
new Object [] { 100, 1125, 25  },
};
}

@Test(dataProvider = "gcd")
public void verifySolution(int pA, int pB, int pExpected) {
Assert.assertEquals(solution.gcdBySubtraction(pA, pB), pExpected);
}

@Test(dataProvider = "gcd")
public void verifySolution2(int pA, int pB, int pExpected) {
Assert.assertEquals(solution.gcdByDivision(pA, pB), pExpected);
}
}

```