**Problem Statement:** Find the gcd of two numbers.

##
**
Examples
**

Example 1:Input:num1 = 4, num2 = 8Output:4Explanation:Since 4 is the greatest number which divides both num1 and num2.Example 2:Input:num1 = 3, num2 = 6Output:3Explanation:Since 3 is the greatest number which divides both num1 and num2.

**Practice:**

** Disclaimer**:

*Don’t jump directly to the solution, try it out yourself first.*

## Brute Force Approach

## Algorithm / Intuition

**Solution 1: Brute force**

**Intuition: **Simply traverse from 1 to min(a,b) and check for every number.

**Approach**:

- Traverse from 1 to min(a,b).
- And check if i is divisible by both a and b.If yes store it in the answer.
- Find the maximum value of i which divides both a and b.

## Code

```
#include<bits/stdc++.h>
using namespace std;
int main()
{
int num1 = 4, num2 = 8;
int ans;
for (int i = 1; i <= min(num1, num2); i++) {
if (num1 % i == 0 && num2 % i == 0) {
ans = i;
}
}
cout << "The GCD of the two numbers is "<<ans;
}
```

Output: The GCD of the two numbers is 4

```
public class Main {
public static void main(String args[]) {
int num1 = 3, num2 = 6;
int ans = 1;
for (int i = 1; i <= Math.min(num1, num2); i++) {
if (num1 % i == 0 && num2 % i == 0) {
ans = i;
}
}
System.out.print("The GCD of the two number is "+ans);
}
}
```

Output: The GCD of the two numbers is 4

```
if __name__ == '__main__':
num1 = 4
num2 = 8
ans = 1
for i in range(1, min(num1, num2) + 1):
if num1 % i == 0 and num2 % i == 0:
ans = i
print("The GCD of the two numbers is", ans)
```

Output: The GCD of the two numbers is 4

```
let num1 = 4, num2 = 8;
let ans;
for (let i = 1; i <= Math.min(num1, num2); i++) {
if (num1 % i === 0 && num2 % i === 0) {
ans = i;
}
}
console.log("The GCD of the two numbers is " + ans);
```

Output: The GCD of the two numbers is 4

## Complexity Analysis

**Time Complexity: **O(N).

**Space Complexity:** O(1).

## Optimal Approach

## Algorithm / Intuition

**Solution 2: Using Euclidean’s theorem.**

**Intuition: **Gcd is the greatest number which is divided by both a and b.If a number is divided by both a and b, it is should be divided by (a-b) and b as well.

**Approach:**

- Recursively call gcd(b,a%b) function till the base condition is hit.
- b==0 is the base condition.When base condition is hit return a,as gcd(a,0) is equal to a.

## Code

```
#include<bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
int main()
{
int a = 4, b = 8;
cout <<"The GCD of the two numbers is "<<gcd(a, b);
}
```

Output: The GCD of the two numbers is 4

```
public class Main {
static int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
public static void main(String args[]) {
int a = 4, b = 8;
int ans = gcd(a, b);
System.out.print("The GCD of the two numbers is "+ans);
}
}
```

Output: The GCD of the two numbers is 4

```
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
if __name__ == "__main__":
a = 4
b = 8
print("The GCD of the two numbers is", gcd(a, b))
```

Output: The GCD of the two numbers is 4

```
let num1 = 4, num2 = 8;
let ans;
for (let i = 1; i <= Math.min(num1, num2); i++) {
if (num1 % i === 0 && num2 % i === 0) {
ans = i;
}
}
console.log("The GCD of the two numbers is " + ans);
```

Output: The GCD of the two numbers is 4

## Complexity Analysis

<

**Time Complexity:** O(log_{ɸ}min(a,b)), where ɸ is 1.61.

**Space Complexity:** O(1).

## Video Explanation

Special thanks to Pranav PadaweandSudip Ghoshfor contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam,please check out this article