GCD and the Euclidean Algorithm

The greatest common divisor gcd(a, b) is the largest positive integer dividing both. Euclid: gcd(a, 0) = |a|, gcd(a, b) = gcd(b, a % b). Each remainder is at least a Fibonacci-smaller, so the worst case is O(log a).

LCM: lcm(a, b) = a / gcd(a, b) * b — divide before you multiply or you overflow. C++ std::gcd / JS we write the loop (or BigInt if needed). CSES Common Divisors and every 'make the array equal by subtracting' problem start here.

Euclid, then gcd of an arrayjs

function gcd(a, b) {
  a = Math.abs(a);
  b = Math.abs(b);
  while (b) {
    const t = a % b;
    a = b;
    b = t;
  }
  return a;
}

function gcdArray(a) {
  return a.reduce((g, x) => gcd(g, x), 0);
}

TRACE

gcd(48, 18).

48, 18

48 = 2·18 + 12. Next (18, 12).

1 / 4

CHECK

You may subtract any other element from an element. Can you make the array all zeros?

WA modes:

- gcd(0, 0) is defined as 0 here; some libraries throw. Empty array → 0. - a / gcd * b vs a * b / gcd. The second overflows int at 1e9 × 1e9. - Using floats (a % b with doubles) — remainders lie. - Math.abs(Number.MIN_SAFE_INTEGER) is not safe. Stay inside the arena's bounds or use BigInt.

CHECK

lcm(a, b, c). Which association is safe?

Checks 0/2

Next lesson