Greatest Common Divisor

Concept

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

For 12 and 8:

• Factors of 12: 1, 2, 3, 4, 6, 12
• Factors of 8: 1, 2, 4, 8
• The common factors are 1, 2, 4. The Greatest is 4.

The Naive Approach

You could write a for loop starting from Math.min(a, b) and counting down to 1. The very first number where a % i === 0 && b % i === 0 is the answer.
This is $O(N)$ time. If the numbers are in the billions, this is too slow.

The Optimal Approach: Euclidean Algorithm

Around 300 BC, the Greek mathematician Euclid proved a flawless mathematical shortcut:
The GCD of two numbers A and B is exactly the same as the GCD of B and the remainder of A % B.

If we continuously replace A with B, and B with A % B, the numbers will rapidly shrink.
The exact moment B hits 0, the number left in A is the absolute Greatest Common Divisor!

The Mechanism

Find the GCD of 48 and 18.

1. A = 48, B = 18.
2. Modulo: 48 % 18 = 12.
3. Shift: A becomes 18, B becomes 12.
4. Modulo: 18 % 12 = 6.
5. Shift: A becomes 12, B becomes 6.
6. Modulo: 12 % 6 = 0.
7. Shift: A becomes 6, B becomes 0.
8. B is 0! The loop stops. A is 6. The answer is 6!

Implementation

The Euclidean algorithm is famously one of the shortest and most elegant algorithms in computer science.

// Time Complexity: O(log(min(A, B))) (Incredibly fast)
// Space Complexity: O(1) Iterative, O(log N) Recursive

// Iterative (Preferred for O(1) Space)
function gcd(a: number, b: number): number {
    while (b !== 0) {
        const remainder = a % b;
        a = b;
        b = remainder;
    }
    return a;
}

// Recursive (The famous 1-liner)
function gcdRecursive(a: number, b: number): number {
    if (b === 0) return a;
    return gcdRecursive(b, a % b);
}

Least Common Multiple (LCM)

The Least Common Multiple (LCM) is the absolute smallest number that can be perfectly divided by both A and B.
For 4 and 6, the multiples are:

• 4: 4, 8, 12, 16, 20...
• 6: 6, 12, 18, 24...
  The absolute lowest common number is 12.

If you already know the GCD formula, calculating the LCM requires exactly one line of math:
LCM = (A $\times$ B) / GCD(A, B)

function lcm(a: number, b: number): number {
    // Optimization: Divide before multiplying to prevent Integer Overflow!
    // (a / gcd) * b   is mathematically identical to   (a * b) / gcd
    return (a / gcd(a, b)) * b; 
}

Interview Questions

Q: In the Euclidean algorithm, what happens if A is smaller than B? (e.g., gcd(18, 48))
A: It fixes itself instantly on the very first loop!
18 % 48 evaluates to 18.
A becomes 48, and B becomes 18.
The algorithm automatically swapped the variables so the larger number is in front, and then proceeds normally. You never need to write an if (a < b) check!

Q: Where does GCD actually show up in modern interviews?
A: It appears in “Fraction Simplification” algorithms. If you are asked to add 1/4 and 1/6, you must find a common denominator (which is the LCM). To simplify the final fraction 5/12, you must divide the numerator and denominator by their GCD.
It also appears in Geometry problems (e.g., finding how many physical integer coordinates a line passes through on a 2D grid uses GCD).