Greatest Common Divisor InterviewBit Solution

Problem: Greatest Common Divisor

Problem Description:

Given 2 non-negative integers m and n, find gcd(m, n)

GCD of 2 integers m and n is defined as the greatest integer g such that g is a divisor of both m and n.
 Both m and n fit in a 32 bit signed integer.

Example

m : 6
 n : 9
 GCD(m, n) : 3

We need to find the greatest common divisor. For that, we can use the famous Euclidean Algorithm.

Time Complexity: O(logN)

Space Complexity: O(1)

Code in C++