GCD and LCM — Euclidean Algorithm Deep Dive for FAANG Interviews

Problem Statement#

Given an integer array nums, return the greatest common divisor of the smallest number and largest number in nums. The GCD of two numbers is the largest positive integer that evenly divides both.

Constraints:

• 2 <= nums.length <= 1000
• 1 <= nums[i] <= 1000

Input:  nums = [2, 5, 6, 9, 10]
Output: 2
Explanation: min = 2, max = 10. GCD(2, 10) = 2.

Input:  nums = [7, 5, 6, 8, 3]
Output: 1
Explanation: min = 3, max = 8. GCD(3, 8) = 1.

Why This Problem Matters#

GCD is the bedrock of number theory. It appears directly in LCM computation, fraction simplification, modular inverse, Bezout's identity, and the Chinese Remainder Theorem. At Google and Meta, interviewers use GCD problems to test whether you can reduce a problem to a mathematical property rather than brute-force it.

LC 1979 is intentionally easy — the real interview value comes from the follow-up: "Now what if you needed GCD of all elements? What if you needed LCM? What if you needed modular inverse?" Each follow-up builds on the same Euclidean foundation.

The Core Insight#

GCD(a, b) = GCD(b, a mod b). This is Euclid's algorithm. Any common divisor of a and b also divides a mod b = a - floor(a/b) * b because divisors are closed under linear combinations. The set of common divisors of (a, b) is identical to the set of common divisors of (b, a mod b). The algorithm terminates because a mod b < b, so the second argument strictly decreases each step.

The number of steps is at most 2 * log_phi(max(a, b)) — fewer than 90 steps for any 64-bit integers.

LCM pitfall: LCM(a, b) = a * b / GCD(a, b). If you compute a * b first, you overflow for a, b near 10^9. Always write a / GCD(a, b) * b — divide first to eliminate the common factor before multiplying.

Visual Dry Run#

GCD(48, 18):

LCM(48, 18): 48 / 6 * 18 = 8 * 18 = 144. Verify: 144 / 48 = 3, 144 / 18 = 8. Both integers. Correct.

Solution (Optimal)#

from math import gcd
 
def findGCD(nums: list[int]) -> int:
    return gcd(min(nums), max(nums))   # O(n) scan + O(log min) GCD
 
# Standalone iterative GCD for interview clarity
def euclidean_gcd(a: int, b: int) -> int:
    while b:
        a, b = b, a % b   # replace (a,b) with (b, a mod b)
    return a              # when b=0, a holds the GCD
 
def safe_lcm(a: int, b: int) -> int:
    return a // euclidean_gcd(a, b) * b   # divide FIRST to avoid overflow
 
def gcd_of_array(nums: list[int]) -> int:
    result = nums[0]
    for num in nums[1:]:
        result = euclidean_gcd(result, num)
        if result == 1:
            return 1   # GCD can never decrease below 1; early exit
    return result

function findGCD(nums) {
    function gcd(a, b) {
        while (b !== 0) {
            [a, b] = [b, a % b];
        }
        return a;
    }
 
    let minVal = nums[0], maxVal = nums[0];
    for (const num of nums) {
        if (num < minVal) minVal = num;
        if (num > maxVal) maxVal = num;
    }
    return gcd(minVal, maxVal);
}
 
function safeLcm(a, b) {
    function gcd(a, b) {
        while (b !== 0) { [a, b] = [b, a % b]; }
        return a;
    }
    return (a / gcd(a, b)) * b;  // divide first; JS handles up to 2^53 exactly
}

Time: O(n) — dominated by the linear scan for min and max; GCD itself is O(log min) Space: O(1) — no additional allocation

Common Mistakes#

• Computing a * b before dividing in LCM. For a = b = 10^9 the product is 10^18, which overflows 32-bit integers. Always divide first: a / gcd(a, b) * b.
• Forgetting gcd(0, n) = n. This is the base case. Zero is divisible by every integer, so any n divides both 0 and n.
• Using % with negative numbers. In C++ and Java, -7 % 3 = -1 (sign follows dividend). Take abs(a) and abs(b) before the algorithm.
• Applying GCD to floats. GCD is defined for integers only. Convert rational numbers to integer form first.
• LCM overflow for arrays. LCM(a1, ..., an) grows exponentially. Always apply modulo when the problem allows it.
• Confusing GCD of an array with pairwise GCD. Reduce left to right: GCD(GCD(...GCD(a1, a2), a3)..., an). GCD is associative, so this is correct.

Interview Tips#

• Write the iterative Euclidean GCD, not the recursive version — it avoids stack overflow for large inputs.
• Mention the early exit when result == 1 in GCD of array — GCD can only decrease, never go below 1.
• Proactively mention the LCM overflow trap and show a // gcd(a, b) * b.

Follow-up Questions#

• How do you compute modular inverse using GCD? Use the Extended Euclidean Algorithm to find x, y such that a*x + b*y = GCD(a, b). If GCD(a, m) = 1, then x is the modular inverse. In Python 3.8+: pow(a, -1, m).
• GCD of Strings (LC 1071). How does GCD apply to strings? The "GCD" string is the longest string x such that both s and t are repetitions of x. It exists iff s + t == t + s. When it exists, the answer is s[:GCD(len(s), len(t))].
• Nth Magical Number (LC 878). How does LCM help? Count of magical numbers up to x is x/a + x/b - x/LCM(a,b) by inclusion-exclusion. Binary search on x.
• What is Bezout's Identity? For any integers a, b, there exist x, y such that a*x + b*y = GCD(a, b). This is the theoretical foundation of the modular inverse and CRT. The Extended Euclidean algorithm computes these x, y alongside the GCD.

Key Takeaways#

• The Euclidean algorithm computes GCD in O(log n) steps via GCD(a, b) = GCD(b, a mod b).
• The algorithm is both ancient (240 BC) and optimal — no algorithm can compute GCD faster in the worst case.
• For LCM, always divide before multiplying to prevent overflow: a // gcd(a, b) * b.
• gcd(0, n) = n is the base case — zero is divisible by everything.
• The Extended Euclidean algorithm computes Bezout coefficients alongside GCD, enabling modular inverses and CRT.
• GCD of an array reduces left to right in n-1 calls; early exit when result = 1 saves work.
• Every number theory problem involving divisibility traces back to GCD in some form.