Skip to content
Hello Python
Algorithm1 Practice1 Interview

Euclidean GCD

Repeatedly replace a pair by divisor and remainder to compute the greatest common divisor. Learn the algorithm's preconditions, state transition, correctness argument, Python cost model, and transfer from one focused drill to a full Interview Problem.

Recognize it when

Consider Euclidean GCD when the prompt's constraints and required operations match this shape: Repeatedly replace a pair by divisor and remainder to compute the greatest common divisor.

Pybit demonstrates Euclidean GCD in a professional Python interview workspace.
On this page · Replace a Pair Without Changing Divisors

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Euclidean GCD Code Labs

Replace a Pair Without Changing Divisors

The common divisors of a and b are exactly the common divisors of b and a modulo b. This identity lets Euclid replace the pair with a strictly smaller second value.

Reduce by Remainders

Repeat a, b = b, a mod b until b is zero. The last nonzero a is the greatest common divisor, and the remainder decrease proves logarithmic termination.

Trace Euclidean Remainders

Reference
def gcd_trace(a,b):
    a,b=abs(a),abs(b);trace=[]
    while b:trace.append([a,b,a%b]);a,b=b,a%b
    return trace
Practice

Implement gcd_trace(a,b). Normalize signs and return [a,b,a%b] until b becomes zero.

Public tests

  • Preserve common divisors across remainders

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Normalize Zero and Signs

Return a nonnegative gcd by taking absolute values. gcd(a, 0) is abs(a), and gcd(0, 0) is conventionally zero in programming libraries.

Compute GCD of Many Values

Reference
def gcd_many(values):
    result=0
    for value in values:
        a,b=result,abs(value)
        while b:a,b=b,a%b
        result=a
    return result
Practice

Implement gcd_many(values). Return the nonnegative greatest common divisor, with 0 for empty input.

Public tests

  • Fold normalized pairwise gcd

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Connect GCD to LCM and Fractions

Use lcm(a,b) = abs(a // gcd(a,b) * b), guarding the all-zero case and dividing before multiplication. GCD also reduces fractions and normalizes ratios.

Explain It in an Interview

Say: “Replacing (a,b) with (b,a mod b) preserves every common divisor while shrinking the second argument.” Trace one remainder sequence, normalize signs, and state O(log min(a,b)) time.

Python Version Note

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

OperationAverageWorstInterview note
Euclidean GCD complete workflowO(log min(a,b))O(log min(a,b))Normalize signs and repeatedly replace (a,b) by (b,a mod b).

Space

O(1) for the focused Compute GCD with Euclid implementation.

Assumptions

  • 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.
  • The bound counts Python sorting, slicing, hashing, heap, recursion, and container-copy costs rather than treating syntax as free.

Invariants Worth Saying Aloud

  1. State the precise Euclidean GCD invariant before coding and preserve it after every update, traversal step, or recursive return.
  2. The transformed state is equivalent to the original query under the documented number rule.
  3. Each update strictly reduces the remaining range or unresolved magnitude.
  4. Preserve the set of common divisors across remainder reduction. Preserve this claim after every transition.
  5. Normalize the result to nonnegative. Preserve this claim after every transition.

When To Use Or Avoid Euclidean GCD

Use It When

  • Use Euclidean GCD when this precondition is stated or can be proved: The integer domain and divisibility, primality, or congruence contract are explicit.
  • Use it when this maintained state removes repeated work: The transformed state is equivalent to the original query under the documented number rule.

Choose Another Tool When

  • Avoid Euclidean GCD when this precondition is absent: The integer domain and divisibility, primality, or congruence contract are explicit.
  • Avoid it when a simpler direct scan satisfies the constraints with less implementation risk.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Applying the algorithm without its precondition

Verify algorithm preconditions such as sorted input, nonnegative weights, acyclicity, or admissible heuristics before applying it.

Prevent it: State and verify this precondition before coding: The integer domain and divisibility, primality, or congruence contract are explicit.

Avoid

def greatest_common_divisor(left, right):
    pass

Use instead

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

Where you will hit this: Compute GCD with Euclid(opens in a new tab)

Breaking the state transition

Returns the smaller input instead of reducing by remainders.

Prevent it: Preserve this proof obligation: Each transformation preserves the required number-theoretic relation while moving toward a terminal bound.

Avoid

def greatest_common_divisor(a,b):
    return min(abs(a),abs(b))

Use instead

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

Where you will hit this: Compute GCD with Euclid(opens in a new tab)

Hiding Python work in the claimed bound

Include visited state, boundary cases, recursion depth, and hidden copying costs in correctness and complexity analysis.

Prevent it: Count every sort, slice, copy, membership check, heap update, and recursive frame before claiming O(log min(a,b)).

Avoid

def greatest_common_divisor(a,b):
    return min(abs(a),abs(b))

Use instead

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

Where you will hit this: Insert GCD Nodes in a Linked List(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.