> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/maths/greatest-common-divisor.md).

# Greatest Common Divisor

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

```java
public class Solution {
    public int gcd(int A, int B) {
        if (B > A) {
            int temp = A;
            A = B;
            B = temp;
        }
        if (B == 0)
            return A;
        return gcd(B, A % B);
    }
}
```