AntInLoop

GCD, LCM & Extended Euclidean Algorithm Code Implementations

Complete GCD, LCM & Extended Euclidean Algorithm code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.

Read GCD, LCM & Extended Euclidean Algorithm Guide ยท Launch Interactive Visualizer

C++ Implementation

// GCD and LCM Implementation in C++
#include <iostream>
#include <cstdlib>

class GcdLcm {
public:
    // Euclidean algorithm for GCD
    static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return std::abs(a);
    }

    // LCM using GCD
    static int lcm(int a, int b) {
        return std::abs(a * b) / gcd(a, b);
    }
};

CPP Implementation

Time: O(log(n)) | Space: O(1)

gcd

#include <iostream>
#include <algorithm>
using namespace std;
class GCDLCM {
public:
    // Euclidean Algorithm for GCD
    int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    
    // Recursive version
    int gcdRecursive(int a, int b) {
        if (b == 0) return a;
        return gcdRecursive(b, a % b);
    }
    
    // LCM using GCD
    int lcm(int a, int b) {
        return (a / gcd(a, b)) * b;
    }
    
    // Extended Euclidean Algorithm
    pair<int, pair<int, int>> extendedGcd(int a, int b) {
        if (b == 0) {
            return {a, {1, 0}};
        }
        
        auto result = extendedGcd(b, a % b);
        int gcd = result.first;
        int x = result.second.second;
        int y = result.second.first - (a / b) * result.second.second;
        
        return {gcd, {x, y}};
    }
    
    // GCD of multiple numbers
    int gcdMultiple(const vector<int>& numbers) {
        int result = numbers[0];
        for (int i = 1; i < numbers.size(); i++) {
            result = gcd(result, numbers[i]);
        }
        return result;
    }
    
    // LCM of multiple numbers
    int lcmMultiple(const vector<int>& numbers) {
        int result = numbers[0];
        for (int i = 1; i < numbers.size(); i++) {
            result = lcm(result, numbers[i]);
        }
        return result;
    }
};

JAVA Implementation

// GCD and LCM Implementation in Java
public class GcdLcm {

    // Euclidean algorithm for GCD
    public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return Math.abs(a);
    }

    // LCM using GCD
    public static int lcm(int a, int b) {
        return Math.abs(a * b) / gcd(a, b);
    }
}

JAVASCRIPT Implementation

// GCD and LCM Implementation in JavaScript

// Euclidean algorithm for GCD
function gcd(a, b) {
  while (b !== 0) {
    [a, b] = [b, a % b];
  }
  return Math.abs(a);
}

// LCM using GCD
function lcm(a, b) {
  return Math.abs(a * b) / gcd(a, b);
}

PYTHON Implementation

# GCD and LCM Implementation in Python

# Euclidean algorithm for GCD
def gcd(a, b):
    while b:
        a, b = b, a % b
    return abs(a)

# LCM using GCD
def lcm(a, b):
    return abs(a * b) // gcd(a, b)