Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Base case `b == 0` returns `a`; else return `gcd(b, a % b)`. Euclid's algorithm — O(log min(a,b)).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you know Euclid recursively and justify the mod-reduction invariant.
Where candidates slip
Wrong argument order, or a broken base case.
How to stand out
Derive LCM from this and note the O(log) convergence.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
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 1 · Optimal
Euclid's algorithm
1Hint 1Explore hintHide hint
Express gcd(a,b) using b and the remainder a mod b.
2Hint 2Explore hintHide hint
What pair makes the recursion stop?
3Hint 3Explore hintHide hint
Why does replacing a with a mod b keep the GCD the same?
A · Core idea
Euclid's algorithm expressed recursively: gcd(a, b) = gcd(b, a mod b), with base case gcd(a, 0) = a.
Why mod-reduction preserves the GCD. Any common divisor of a and b also divides a mod b (= a − ⌊a/b⌋·b), and vice versa, so the pair (a, b) and (b, a mod b) share the same set of common divisors — hence the same greatest one. Each step shrinks the numbers fast.
Why the base case is b == 0. Every integer divides 0, so gcd(a, 0) = a. When the remainder reaches 0, the previous divisor is the answer, which the recursion returns automatically.
Why O(log) depth. The remainder at least halves every two steps, so the recursion bottoms out in logarithmic depth — far fewer calls than testing divisors. LCM follows immediately: lcm(a,b) = a/gcd·b.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
a = 48, b = 18gcd(48,18)
→ gcd(18,12)
126C · Code with teaching comments
D · Why it works and complexityO(log min(a,b)) timeO(log) stack spaceOpen the invariant and proofExplore the proofHide the proof
LCM follows immediately: lcm(a,b) = a / gcd(a,b) * b.
ComplexityO(log min(a,b)) time, O(log) stack space — the remainder shrinks geometrically, so O(log min(a,b)) recursive calls.
E · Edge cases and pitfalls5a = 7, b = 0 — Base case → 7.Explore edge casesHide edge cases
Edge cases handled
a = 7, b = 0Base case → 7.a = 5, b = 1Coprime → 1.a = 0, b = 5First call swaps to gcd(5, 0) → 5.
Pitfalls
- Swapping the arguments wrongly (gcd(a % b, b) loops).
- Dividing by zero by mishandling b == 0.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic long gcd(long a, long b) { if (b == 0) return a; return gcd(b, a % b); }Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
- Swapping the arguments wrongly (gcd(a % b, b) loops).
- Dividing by zero by mishandling b == 0.
Revise
Carry the pattern into the interview
Pattern to remember
Euclid's algorithm
Code pattern to memorize
gcd(a,b) = b==0 ? a : gcd(b, a%b)Rules to remember
- 1gcd(a,0)=a.
- 2gcd(a,b)=gcd(b,a%b).
- 3O(log) steps.
Use this pattern when
- GCD/LCM
- Fraction reduction
Interview takeaway
Euclid: replace the pair with (b, a mod b) until b is 0.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternA core fresher pattern: Euclid's algorithm. Master it on small inputs and it transfers to harder problems.
Practice queueDirect variations and pattern siblings
Direct follow-ups