Find GCD of two numbers - Tutorial [Updated]

Problem Statement: Find 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.

Solution

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

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:

C++ 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

Time Complexity: O(N).

Space Complexity: O(1).

Java Code

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 3

Time Complexity: O(N).

Space Complexity: O(1).

Python Code

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

Time Complexity: O(N).

Space Complexity: O(1).

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:

C++ 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

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

Space Complexity: O(1).

Java Code

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

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

Space Complexity: O(1).

Python Code

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

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

Space Complexity: O(1).

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