Problem

Given 2 numbers, calculate the GCD of them. Here is problem in details: Find GCD of two numbers.

Solution

The Euclidean algorithm involves repeatedly dividing and taking the remainder until the remainder is 0. The non-zero divisor at this step is the GCD.

Here is the approach:

  1. Divide the larger number by the smaller number and take the remainder.
  2. Replace the larger number with the smaller number and the smaller number with the remainder.
  3. Continue until the remainder is 0.
  4. The non-zero number at this step is the GCD.

Method 1 - Recursive

Code

Java
public class RecursiveBasicEuclideanGCD {
    
    public int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
}
Python
class RecursiveBasicEuclideanGCD:
    
    def gcd(self, a, b):
        if b == 0:
            return a
        return self.gcd(b, a % b)

Complexity

  • ⏰ Time complexity: O(NNNXXXNNN)
  • 🧺 Space complexity: O(NNNXXX)

Method 2 - Iterative

Code

Java
public class BasicEuclideanGCD {
    public int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}
Python
class BasicEuclideanGCD:
    def gcd(self, a, b):
        while b != 0:
            a, b = b, a % b
        return a

Complexity

  • ⏰ Time complexity: O(log(min(a, b)))
  • 🧺 Space complexity: O(1)