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(NNNXXXNNN)
  • 🧺 Space complexity: O(NNNXXX)

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)