Greatest Common Divisor ( GCD )

GCD (Greatest Common Divisor) is the largest positive integer that divides two or more positive integers without leaving a remainder.

Here are different ways to calculate GCD in C++ with their time and space complexities:

Euclidean algorithm:

Time complexity: O(log(min(a, b))), where a and b are the two numbers whose GCD is to be found.

Space complexity: O(1)

Implementation:


int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

Standard library function:

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

Space complexity: O(1)

Implementation:


#include <numeric>
int gcd = __gcd(a, b);

Binary GCD algorithm:

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

Space complexity: O(1)

Implementation:


int gcd(int a, int b) {
    if (a == b) {
        return a;
    }
    if (a == 0) {
        return b;
    }
    if (b == 0) {
        return a;
    }
    if (~a & 1) {
        if (b & 1) return gcd(a >> 1, b);
        else return gcd(a >> 1, b >> 1) << 1;
    }
    if (~b & 1) return gcd(a, b >> 1);
    if (a > b) return gcd((a - b) >> 1, b);
    return gcd((b - a) >> 1, a);
}

In all these implementations of GCD, the time complexity is logarithmic to the minimum of the two input numbers, whereas the space complexity is constant as only a few variables are being used throughout the algorithm. The binary GCD algorithm is faster than Euclidean algorithm for large inputs, but its implementation is more complex and it is not recommended to use for small inputs.

PRACTICE PROBLEMS :

Find Greatest Common Divisor of Array

GCD Sort of an array