Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Use the Euclidean algorithm: repeatedly replace (a, b) with (b, a % b) until b becomes 0; the remaining a is the GCD. It runs in O(log(min(a, b))) — exponentially faster than the subtraction version or trial division.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you know the Euclidean algorithm and reach for the modulo form (not subtraction or factorization), and whether you get the base case gcd(a, 0) = a right.
Where candidates slip
Using repeated subtraction (correct but exponentially slow), or recursing with the wrong base case, or forgetting that gcd(a, 0) = a.
How to stand out
Recite gcd(a, b) = gcd(b, a % b), state the O(log min) bound, and immediately connect it to LCM = a / gcd * b — dividing before multiplying to avoid overflow.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewCompute gcd(a, b)Repeated subtraction or modulo?SubtractionModuloExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Repeated Subtraction (Baseline)
1Hint 1Explore hintHide hint
Any number dividing both a and b also divides their difference. What does that let you replace the larger number with?
2Hint 2Explore hintHide hint
Repeatedly subtract the smaller from the larger; the common divisors never change.
3Hint 3Explore hintHide hint
Stop when the two numbers are equal — that value is the GCD. But ask: how many subtractions does gcd(1, 1e9) take?
A · Core idea
Euclid's original formulation: while the two numbers differ, subtract the smaller from the larger. Their set of common divisors is invariant under this step, so when the numbers become equal, that shared value is the GCD.
Why subtraction preserves the GCD. If d divides both a and b, then d also divides a − b (and b). So gcd(a, b) = gcd(a − b, b). Repeatedly applying this never loses or gains a common divisor — it just shrinks the numbers while keeping the answer fixed.
Why it's correct but too slow. The logic is airtight, but consider gcd(1, 1_000_000_000). You subtract 1 from the big number one at a time — a billion iterations. The running time is proportional to the magnitude of the inputs, not their digit count, which is exponentially worse than it needs to be.
The fix that motivates the optimal. Subtracting b from a over and over until a < b is exactly computing a % b in one step. Replacing the inner subtraction loop with a single modulo operation collapses many iterations into one — that's the entire jump from this baseline to the Euclidean algorithm.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
a = 48, b = 18Array state
1
48 − 18 → 30
6C · Code with teaching comments
Reference implementation previewpublic int gcdSubtract(int a, int b) { a = Math.abs(a); b = Math.abs(b); if (a == 0) return b; if (b == 0) return a;Explore the full codeHide the full code
D · Why it works and complexityO(max(a, b)) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Repeated subtraction down to below b is just the modulo operation done the slow way. Seeing that equivalence is what tells you to swap the subtraction loop for a single %.
ComplexityO(max(a, b)) time, O(1) space — Each step shrinks the larger number by at most the smaller. For lopsided pairs like (1, 10⁹) you subtract 1 a billion times → O(max(a, b)) in the worst case.
E · Edge cases and pitfalls3Timing out on lopsided inputs like gcd(1, 10⁹) — a billion subtractions.Explore edge casesHide edge cases
Pitfalls
- Timing out on lopsided inputs like gcd(1, 10⁹) — a billion subtractions.
- Looping forever if a 0 input isn't guarded (subtracting 0 never changes anything).
- Forgetting abs() on negative inputs.
Approach 2 of 2 · Optimal
Euclidean Algorithm with Modulo (Optimal)
1Hint 1Explore hintHide hint
Subtracting b from a repeatedly until a < b is the same as one modulo operation. What does that suggest replacing the inner loop with?
2Hint 2Explore hintHide hint
Set a, b = b, a % b each step. The pair shrinks, and gcd is preserved because any common divisor of a and b divides a % b too.
3Hint 3Explore hintHide hint
Stop when b becomes 0; the answer is the current a. This is O(log) because the remainder at least halves every two steps (a classic Fibonacci-worst-case result).
A · Core idea
Replace the slow subtraction chain with a single modulo: at each step set (a, b) = (b, a % b) and stop when b reaches 0. The surviving a is the GCD.
Why gcd(a, b) = gcd(b, a % b). Write a = q·b + r where r = a % b. Any divisor d of both a and b must divide r = a − q·b, and conversely any divisor of b and r divides a. So the pair (a, b) and the pair (b, r) have exactly the same common divisors — and therefore the same greatest one. Each modulo step shrinks the numbers without changing the answer.
Why the base case is gcd(a, 0) = a. Every integer divides 0, so the common divisors of a and 0 are just the divisors of a, the greatest of which is a itself. When b becomes 0, you stop and return a. This also means an input of b = 0 returns a immediately, and gcd(0, 0) returns 0.
Why it's logarithmic. Modulo does in one step what subtraction needed many for. Lamé's theorem shows the worst case happens on consecutive Fibonacci numbers, and there the smaller value shrinks by a constant factor roughly every step — so the number of iterations is O(log of the smaller input). That's why gcd(1, 10⁹) finishes in two steps, not a billion.
Why order doesn't matter. If you call it with a < b, the first iteration computes a % b == a, which effectively swaps the pair to (b, a). So you never need to pre-sort the arguments.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
a = 48, b = 18Array state
1
(48, 18) → (18, 12)
6C · Code with teaching comments
D · Why it works and complexityO(log min(a, b)) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
GCD is preserved under taking remainders, and the remainder shrinks geometrically — that's the whole reason a handful of modulo steps replaces a billion subtractions. Pair it with lcm = a / gcd * b (divide before multiplying) and you cover the entire common-divisor toolkit.
ComplexityO(log min(a, b)) time, O(1) space — Each two iterations at least halve the smaller value (Lamé's theorem ties the worst case to consecutive Fibonacci numbers), giving O(log min(a, b)) modulo operations.
E · Edge cases and pitfalls6a = 0, b = 9 — First step: (0, 9) → (9, 0). Returns 9. The a < b case self-corrects.Explore edge casesHide edge cases
Edge cases handled
a = 0, b = 9First step: (0, 9) → (9, 0). Returns 9. The a < b case self-corrects.a = 9, b = 0Loop never runs (b == 0); returns 9 immediately.a = 0, b = 0Loop never runs; returns 0 — the conventional value for gcd(0, 0).
Pitfalls
- Recursing or looping with the wrong base case (returning b instead of a when b hits 0).
- Computing LCM as a * b / gcd — the a * b product can overflow; divide first.
- Skipping abs() so signed remainders give a negative GCD.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int gcd(int a, int b) { a = Math.abs(a); b = Math.abs(b); while (b != 0) { int r = a % b;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Subtraction instead of modulo
Correct but O(max(a,b)). On gcd(1, 1_000_000_000) it does a billion iterations and times out. Use a % b.
Explore the code comparisonHide the code comparison
Subtraction instead of modulo
Correct but O(max(a,b)). On gcd(1, 1_000_000_000) it does a billion iterations and times out. Use a % b.
Don't write this
while (a != b) {
if (a > b) a -= b; else b -= a;
}
return a; // TLE on gcd(1, 1e9)Write this instead
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return a;2Wrong base case
When b becomes 0 the GCD is a (every number divides 0). Returning b here gives 0 for every input.
Explore the code comparisonHide the code comparison
Wrong base case
When b becomes 0 the GCD is a (every number divides 0). Returning b here gives 0 for every input.
Don't write this
def gcd(self, a: int, b: int) -> int:
while b != 0:
a, b = b, a % b
return b # always 0Write this instead
def gcd(self, a: int, b: int) -> int:
while b != 0:
a, b = b, a % b
return a3LCM overflow
a * b can exceed the integer range before the division. Divide by the GCD first, then multiply.
Explore the code comparisonHide the code comparison
LCM overflow
a * b can exceed the integer range before the division. Divide by the GCD first, then multiply.
Don't write this
return (long) a * b / gcd(a, b); // a * b may overflow int firstWrite this instead
return (long) (a / gcd(a, b)) * b;Revise
Carry the pattern into the interview
Pattern to remember
Euclidean algorithm — gcd(a, b) = gcd(b, a % b) until b = 0
Code pattern to memorize
while b != 0:
a, b = b, a % b
return a # gcd(a, 0) = a is the base caseRules to remember
- 1The base case is
gcd(a, 0) = a— whenbhits 0, the answer is whateveracurrently holds. - 2Use the modulo form (
a % b), not repeated subtraction. Subtraction is O(max(a,b)) and times out on inputs like gcd(1, 10⁹). - 3Take
absof both inputs first — GCD is defined on magnitudes, and signed%differs across languages. - 4
gcd(0, 0)is conventionally0(or undefined) — confirm which the interviewer wants and the loop returns 0 for it naturally. - 5Order doesn't matter: even if
a < b, the first iteration swaps them sincea % b == awhena < b.
Use this pattern when
- Reducing a fraction to lowest terms (divide both by their GCD)
- Computing LCM via lcm(a, b) = a / gcd(a, b) * b
- Any problem about common divisors, tiling a rectangle with squares, or syncing periodic events
- As a subroutine inside modular-inverse and Diophantine-equation solvers (extended Euclid)
Choose another pattern when
- You need the GCD of a whole array → fold gcd across elements, not a pairwise special case
- You also need coefficients x, y with ax + by = gcd → use the *extended* Euclidean algorithm
- Numbers exceed 64 bits → use BigInteger.gcd, which already implements this
Interview takeaway
Euclid's insight — that gcd(a, b) = gcd(b, a % b) — turns common-divisor questions from trial division into a handful of modulo steps. It's the backbone of LCM, fraction reduction, and modular inverses, so the few lines pay off everywhere.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternThe Euclidean algorithm: gcd(a, b) = gcd(b, a % b) with base case gcd(a, 0) = a. It's the canonical 'replace a hard quantity with a smaller equivalent one' reduction, and it underpins LCM, fraction reduction, modular inverses (extended Euclid), and Diophantine equations.
Practice queueDirect variations and pattern siblings
Direct follow-ups