Skip to content

GCD of two numbers

The Greatest Common Divisor (GCD), or Highest Common Factor (HCF), is the largest number that divides two numbers without a remainder.

Calculating Greatest Common Divisors

A naive approach to this is to iterate from all numbers between 1 to $\(\text{min}(m,n)\)$ and return the biggest number that divides them

int gcd(int m, int n) {
    int maxDivisor = 1;
    for (int i = 1; i < min(m,n); ++i) {
        if(m%i == 0 && n%i ==0) {
            maxDivisor = i; 
        }
    }
    return i;
}

Info

The GCD is always positive irrespective of the sign of the input numbers. If the given number is negative, we will simply ignore its - sign using the abs() function

To find the GCD of two numbers using recursion, we will be using the principle $\(\text{GCD}(a,b) = \text{GCD}(a,b−a)\)$

Steps of the Algorithm

  1. Check if a==0, if yes, return b.
  2. Check if b==0, if yes, return a.
  3. Check if a==b, if yes, return a.
  4. Check if a>b if yes, call GCD() function using the arguments a−b and b recursively, otherwise call GCD() function using the arguments a and

Implementation

int gcd(int a , int b) {
  if(a == 0) return b;
  if(b == 0) return a;
  return  a > b ? gcd(a-b,b) : gcd(a,b-a);
}

Complexity Analysis

Time Complexity

\[\text{O}(\text{max}(a,b))$$ In this algorithm, the number of steps are linear, for e.g. $$GCD(x,1)$$ in which we will subtract $$1$$ from $$x$$ in each recursion, so the time complexity will be $$\text{O}(\text{max}(a,b))\]

Space Complexity

The space complexity here is $\(\text{O}(\text{max}(a,b))\)$ because the space complexity in a recursive function is equal to the maximum depth of the call stack.

Comments