# 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
```

## Approach

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

## Time & Space Complexity

`Time Complexity: O(logN)`

`Space Complexity: O(1)`

**Solution:**

Code in C++