Student, Developer, Technology Advocate
Welcome to my personal website

Hackerrank Solution: Computing the GCD

on Nov. 6, 2016, 9:03 p.m.

Given two integers, x and y, a recursive technique to find their GCD is the Euclidean Algorithm.

The algorithm states that, for computing the GCD of two positive integers x and y, if x and y are equal, GCD(x, y) = x. Otherwise GCD(x, y) = GCD(x - y, y) if x > y. There are a few optimizations that can be made to the above logic to arrive at a more efficient implementation.

Given the starter code, you need to complete a function body that returns the GCD of two given integers x and y.
The task of reading in input and printing the output will be handled by us.

Input Format
One line of input containing space separated integers.

Output Format
Output one integer, the GCD of the two given numbers.

Sample Input
1 5

Sample Output

Sample Return Values:

GCD(1,5) = 1
GCD(10,100) = 10
GCD(22,131) = 1


import java.io.*;
import java.util.*;

public class Solution {
public static void main(String[] args) {
Scanner reader = new Scanner(System.in);
int first = reader.nextInt();
int second = reader.nextInt();
System.out.println(gcd(first, second));
public static int gcd(int m, int n){
if(n == 0)
return m;
return gcd(n, m%n);

The code listed above may or may not be the "best" solution. Please be advised that this is just the way I did it. There are normally thousands of different ways to solve the same programming problem. Find an error? Let me know in the contact form below.

Contact Me

Feel free to email me feedback, suggestions, notes, or to just say hello!