GCD using Euclidean Algorithm

Problem Statement

Given two integers a and b, find the Greatest Common Divisor (GCD) also known as the Highest Common Factor (HCF) of the two numbers. The GCD is the largest positive integer that divides both numbers without leaving a remainder.

Example 1: a = 48, b = 18 → Output: 6
Explanation: Divisors of 48 are [1, 2, 3, 4, 6, 8, 12, 16, 24, 48] and divisors of 18 are [1, 2, 3, 6, 9, 18]. The greatest common divisor is 6.

Example 2: a = 54, b = 24 → Output: 6
Example 3: a = 17, b = 13 → Output: 1 (coprime numbers)

Approach 1: Brute Force

Explanation: Iterate from the minimum of the two numbers down to 1, and return the first number that divides both a and b evenly. This is the largest common divisor.

Time Complexity: O(min(a, b))

Space Complexity: O(1)

function gcd(a, b):
    if a == 0:
        return b
    if b == 0:
        return a
    
    minValue = min(a, b)
    for i from minValue down to 1:
        if a % i == 0 and b % i == 0:
            return i
    
    return 1

Approach 2: Euclidean Algorithm (Iterative) - Optimal

Explanation: The Euclidean algorithm is based on the principle that the GCD of two numbers also divides their difference. Instead of computing the difference, we use the modulo operation. We repeatedly replace the larger number with the remainder of dividing the larger by the smaller until one becomes 0.

Key Insight: gcd(a, b) = gcd(b, a mod b)

Time Complexity: O(log(min(a, b)))

Space Complexity: O(1)

function gcd(a, b):
    while b != 0:
        temp = b
        b = a % b
        a = temp
    
    return a

Approach 3: Euclidean Algorithm (Recursive)

Explanation: This is the recursive version of the Euclidean algorithm. The base case is when b becomes 0, at which point a is the GCD. Otherwise, we recursively call gcd with b and a mod b.

Mathematical Property: gcd(a, 0) = a and gcd(a, b) = gcd(b, a mod b)

Time Complexity: O(log(min(a, b)))

Space Complexity: O(log(min(a, b))) - due to recursive call stack 

function gcd(a, b):
    if b == 0:
        return a
    
    return gcd(b, a % b)

Key Properties and Applications

Properties:

Applications: