problemunknownalgorithms

Basic Euclidean Algorithm to find GCD of two numbers using modulo operator

Updated: Sep 29, 2025

Problem

Given 2 numbers, calculate the GCD of them. Here is problem in details: [Find GCD of two numbers](find-gcd-of-two-numbers).

Examples

Example 1:

Input: a = 36, b = 60
Output: 12

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(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

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)

Comments