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

1
2
3
4
5
6
7
8
9

public class RecursiveBasicEuclideanGCD {
    
    public int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
}
1
2
3
4
5
6

class RecursiveBasicEuclideanGCD:
    
    def gcd(self, a, b):
        if b == 0:
            return a
        return self.gcd(b, a % b)

Complexity

  • ⏰ Time complexity: O(log(min(a, b))). Each recursive call reduces the problem size significantly, similar to the number of digits in the smaller number.
  • 🧺 Space complexity: O(log(min(a, b))). Due to the recursion stack, which can go as deep as the number of recursive calls.

Method 2 - Iterative

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

public class BasicEuclideanGCD {
    public int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}
1
2
3
4
5

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)