Compute GCD with Euclid

Practice Exercise Intermediate Medium Array Euclidean GCD

Checking your account…

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement greatest_common_divisor(left, right). Inputs may be negative or zero. Return the nonnegative greatest common divisor.

Starter code

def greatest_common_divisor(left, right):
    pass

Test cases

common-factor

{
  "args": [
    84,
    30
  ]
}

Expected: 6

negative

{
  "args": [
    -24,
    18
  ]
}

Expected: 6

Wizard outline

Step 1: Normalize signs and handle zero
Make the boundary case return the nonzero magnitude. GCD is nonnegative, and gcd(0, n) is the magnitude of n.
Step 2: Reduce a positive pair with remainders
Repeat Euclidean replacement until the remainder is zero. gcd(a, b) equals gcd(b, a % b), so every step preserves the answer.
Step 3: Combine normalization with Euclidean reduction
Support signed inputs without changing the remainder loop. Normalization makes one loop valid for every integer sign combination.

Footguns and prerequisites

Returning a negative divisor violates the result contract.
A subtraction-only loop is needlessly slow for unbalanced inputs.
functions
lists and tuples
control flow

Reviewed references

Python More on Lists

Recommended approach and implementation

Normalize signs and repeatedly replace (a,b) by (b,a mod b).

Why it works: A number divides both a and b exactly when it divides b and a mod b, so every transition preserves common divisors. At b=0, a is therefore the greatest common divisor.

def greatest_common_divisor(left, right):
    left = abs(left)
    right = abs(right)
    while right:
        left, right = right, left % right
    return left