Find GCD of two numbers

Problem Statement: Find the gcd of two numbers.

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

Example 2:
Input: num1 = 3, num2 = 6
Output: 3
Explanation: 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 Optimal Approach

Expand any one approach by clicking the given options in the bar. Clicking one approach on bar, closes all other expands. You can manually expand more than one approach at a time

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 Padawe and Sudip Ghosh for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article