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)
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
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);
}
}