GCD of Two Numbers

Problem Statement

Given two non-negative integers a and b, we have to find their GCD (greatest common divisor),i.e. the largest number which is a divisor of both a and b. It’s commonly denoted by
gcd(a,b).

GCD
Example:

Input: a=32, b=20
Output: 4
Explanation: 4 is the largest factor that divides both of the numbers.

Input: a=98, b=70
Output: 14
Explanation: 14 is the largest factor that divides both of the numbers.

Input: a=399, b=437
Output: 19
Explanation:

Simple Approach

We can traverse over all the numbers from min(A, B) to 1 and check if the current number divides both A and B or not. If it does, then it will be the GCD of A and B.

Efficient Approach: Euclid’s Algorithm

The algorithm is based on the below facts.

When we have to reduce a larger number then what we can do in a simple manner is just subtract small numbers from larger numbers and from this we can notice GCD will not change. Hence we can keep subtracting the larger of two numbers, we end up with the GCD.
Now instead of doing subtraction, we can do one more thing i.e if we divide the smaller number, the algorithm stops when we find remainder 0.

Run the code on Interviewbit - https://www.interviewbit.com/online-java-compiler/
View the full problem from https://www.interviewbit.com/blog/gcd-of-two-numbers/