Loading…

easyMath GeometryFrequently asked

GCD and LCM

Q: How do you solve GCD and LCM using the Common-Divisor Scan (Baseline) approach?

When to use it: Open with this to show you understand the definition before optimising — it makes the Euclidean speed-up land harder. The definition of gcd is 'the largest integer dividing both a and b'. The most direct implementation walks candidate divisors from min(a, b) down to 1 and returns the first one that divides both numbers. **Why start at min(a, b).** No divisor of both a and b can exceed the smaller of the two — a number larger than min(a, b) can't divide min(a, b) at all. So min(a, b) is the largest value worth testing, and scanning downward returns the *greatest* common divisor on the first hit. **Why this is too slow.** For a = 10⁹ and b = 10⁹, the scan can run a billion iterations before finding the gcd. That's linear in the magnitude of the inputs — exponential in their number of digits — which is unacceptable when the Euclidean algorithm settles it in about 30 steps. **What it does teach.** It pins down the definition cleanly: gcd lives in [1, min(a, b)] and divides both. The Euclidean algorithm keeps that exact meaning but reaches the answer geometrically faster by reasoning about remainders instead of testing every candidate. Time complexity: O(min(a, b)). Space complexity: O(1).

Q: How do you solve GCD and LCM using the Euclidean Algorithm + LCM Identity (Optimal) approach?

When to use it: The answer they want. Say 'gcd(a, b) = gcd(b, a mod b)' and immediately note the divide-before-multiply order for LCM. Replace the pair (a, b) with (b, a mod b) repeatedly until the second entry becomes 0; the first entry is then the gcd. LCM is computed afterward as a / gcd * b. **Why gcd(a, b) = gcd(b, a mod b) — the correctness core.** Write a = q·b + r where r = a mod b. Take any common divisor d of a and b. Since d divides a and d divides q·b, it divides their difference a − q·b = r. So d also divides b and r — d is a common divisor of (b, r). Conversely, any common divisor of b and r divides q·b + r = a, so it's a common divisor of (a, b). The two pairs therefore have *exactly the same set of common divisors*, and in particular the same greatest one. Replacing (a, b) with (b, r) leaves the gcd untouched. **Why it terminates fast.** The remainder r = a mod b is strictly less than b, and one can show r < a/2 whenever a swap happens across two steps. So the pair at least halves every two iterations — the number of steps is logarithmic in min(a, b). The classic worst case is consecutive Fibonacci numbers, which is exactly where the step count is largest yet still O(log). **Why the loop ends at b = 0.** gcd(x, 0) = x because every integer divides 0, so the largest common divisor of x and 0 is x itself. When b reaches 0, the surviving a is the gcd. **Why LCM is a / gcd * b, in that order.** From a·b = gcd·lcm we get lcm = a·b / gcd. But a·b can overflow even when lcm fits: with a = b = 10⁹, a·b = 10¹⁸ (borderline for a long) while the lcm might be far smaller. Since gcd divides a exactly, a / gcd is an exact integer, and (a / gcd)·b never exceeds the true lcm — so it stays within range whenever the answer itself does. Writing a * b / gcd instead risks overflowing on the multiply before the divide ever happens. Time complexity: O(log min(a, b)). Space complexity: O(1).

Math & Number Theory · 14 of 36 · 8 min

Given two non-negative integers a and b, compute:

1
Their greatest common divisor gcd(a, b) — the largest integer that divides both.
2
Their least common multiple lcm(a, b) — the smallest positive integer that both divide.

Return both. Use the relationship a * b = gcd(a, b) * lcm(a, b), rearranged carefully to avoid integer overflow.

In plain English

GCD is the biggest number dividing both inputs; LCM is the smallest number both divide into. They're tied by a·b = gcd·lcm, so computing the gcd first hands you the lcm for free. The only subtlety is arithmetic order: a*b can overflow even when the lcm itself fits, so divide by the gcd before multiplying.

Examples

Example 1

Input: a = 12, b = 18
Output: gcd = 6, lcm = 36
Note: Divisors of 12 and 18 share 6 as the largest; lcm = 12 / 6 * 18 = 36.

Example 2

Input: a = 7, b = 13
Output: gcd = 1, lcm = 91
Note: Both prime and distinct → coprime, so gcd = 1 and lcm = 7 * 13 = 91.

Example 3

Input: a = 0, b = 5
Output: gcd = 5, lcm = 0
Note: gcd(0, 5) = 5; lcm is 0 because 0 is a multiple of everything.

Constraints

0 ≤ a, b ≤ 10⁹ (so a*b can reach 10¹⁸ — overflow-aware ordering matters)
gcd(x, 0) = x and gcd(0, 0) = 0 by convention
lcm is 0 if either input is 0
Results are non-negative

Clarifying questions4First question: Can the inputs be zero or negative?Explore questions

Q1.Can the inputs be zero or negative?
I'll assume non-negative. gcd(x, 0) = x, gcd(0, 0) = 0, and lcm with a 0 is 0. For negatives I'd take absolute values, since gcd is conventionally non-negative.
Q2.How large can a and b be — should I worry about overflow?
Up to 10⁹, so a*b reaches 10¹⁸. That fits in a Java long but I still compute lcm as a/gcd*b to keep the intermediate small and safe.
Q3.Do you want an iterative or recursive gcd?
Either is O(log min(a, b)). Iterative avoids recursion-stack overhead and stack-depth worries; I'll show both.
Q4.Is a modular inverse needed anywhere?
Not for plain gcd/lcm. If it were, I'd switch to the extended Euclidean algorithm, which also returns the Bézout coefficients.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

The greatest common divisor comes from the Euclidean algorithm: gcd(a, b) = gcd(b, a mod b), repeating until the second argument hits 0 — then the first is the answer. It runs in O(log min(a, b)). Build LCM on top of it with lcm(a, b) = a / gcd(a, b) * b, and divide BEFORE multiplying so the intermediate never overflows.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you know the Euclidean algorithm cold, can state why gcd(a, b) = gcd(b, a mod b), and whether you order the LCM arithmetic to avoid overflow.

Where candidates slip

Writing lcm as a * b / gcd (overflows for large a, b) instead of a / gcd * b, or looping subtraction instead of using the remainder (turning O(log) into O(max/min)).

How to stand out

Justify correctness: any common divisor of a and b also divides a mod b (and vice versa), so the common-divisor set is invariant — hence the gcd is preserved while the pair shrinks geometrically.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Common-Divisor Scan (Baseline)	`O(min(a, b))`	`O(1)`	Open with this to show you understand the definition before optimising — it makes the Euclidean speed-up land harder.	Read
2	Euclidean Algorithm + LCM Identity (Optimal)Optimal	`O(log min(a, b))`	`O(1)`	The answer they want. Say 'gcd(a, b) = gcd(b, a mod b)' and immediately note the divide-before-multiply order for LCM.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewgcd(a, b)b == 0 ?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Common-Divisor Scan (Baseline)

TimeO(min(a, b))SpaceO(1)

Open with this to show you understand the definition before optimising — it makes the Euclidean speed-up land harder.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

By definition, the gcd is the largest d that divides both a and b. What range must d live in?

2Hint 2Explore hint

Any common divisor is at most min(a, b). So scan d from min(a, b) downward and return the first d that divides both.

3Hint 3Explore hint

Once you have the gcd, the lcm is a / gcd * b. But notice the scan is linear in min(a, b) — what's a faster way to find the gcd?

A · Core idea

The definition of gcd is 'the largest integer dividing both a and b'. The most direct implementation walks candidate divisors from min(a, b) down to 1 and returns the first one that divides both numbers.

Why start at min(a, b). No divisor of both a and b can exceed the smaller of the two — a number larger than min(a, b) can't divide min(a, b) at all. So min(a, b) is the largest value worth testing, and scanning downward returns the greatest common divisor on the first hit.

Why this is too slow. For a = 10⁹ and b = 10⁹, the scan can run a billion iterations before finding the gcd. That's linear in the magnitude of the inputs — exponential in their number of digits — which is unacceptable when the Euclidean algorithm settles it in about 30 steps.

What it does teach. It pins down the definition cleanly: gcd lives in [1, min(a, b)] and divides both. The Euclidean algorithm keeps that exact meaning but reaches the answer geometrically faster by reasoning about remainders instead of testing every candidate.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

a = 12, b = 18

d=12

18 % 12 = 6 ≠ 0

Statenot common

Final resultgcd = 6, lcm = 12 / 6 * 18 = 36

C · Code with teaching comments

Reference implementation previewpublic long gcdScan(long a, long b) { if (a == 0) return b; if (b == 0) return a; long start = Math.min(a, b); for (long d = start; d >= 1; d--) {Explore the full code

solution.javaJava

Common-Divisor Scan (Baseline) — reference

2 teaching notes

1
public long gcdScan(long a, long b) {
2
    if (a == 0) return b;
3
    if (b == 0) return a;
4
    // No common divisor can exceed the smaller input, so start the downward scan there.
5
    long start = Math.min(a, b);
6
    for (long d = start; d >= 1; d--) {
7
        // First d dividing both, scanning down, is the greatest common divisor.
8
        if (a % d == 0 && b % d == 0) {
9
            return d;
10
        }
11
    }
12
    return 1;
13
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.13 lines

D · Why it works and complexityO(min(a, b)) timeO(1) spaceOpen the invariant and proofExplore the proof

The scan is correct and makes the definition concrete, but it's linear in the input magnitude. The leap to Euclid is realising you don't have to test divisors at all — replacing (a, b) with (b, a mod b) preserves the gcd while collapsing the numbers exponentially.

ComplexityO(min(a, b)) time, O(1) space — We test up to min(a, b) candidate divisors, each in O(1), so O(min(a, b)) time and O(1) space.

E · Edge cases and pitfalls3Scanning upward and returning the last hit — wasteful; scanning down returns the gcd immediately.Explore edge cases

Pitfalls

Scanning upward and returning the last hit — wasteful; scanning down returns the gcd immediately.
Running this on 10⁹-scale inputs — O(min(a,b)) is far too slow.
Forgetting the a == 0 / b == 0 guards, which would make min(a, b) = 0 and skip the loop.

03.2

Approach 2 of 2 · Optimal

Euclidean Algorithm + LCM Identity (Optimal)

TimeO(log min(a, b))SpaceO(1)

The answer they want. Say 'gcd(a, b) = gcd(b, a mod b)' and immediately note the divide-before-multiply order for LCM.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Suppose d divides both a and b. Does d also divide a − b? And a mod b? If so, the common divisors of (a, b) and of (b, a mod b) are the same set.

2Hint 2Explore hint

Since the common-divisor set is unchanged, gcd(a, b) = gcd(b, a mod b). Keep replacing the pair until the second number is 0 — then the first is your gcd.

3Hint 3Explore hint

For lcm, use a * b = gcd * lcm, so lcm = a * b / gcd. To avoid overflow, divide first: a / gcd * b.

A · Core idea

Replace the pair (a, b) with (b, a mod b) repeatedly until the second entry becomes 0; the first entry is then the gcd. LCM is computed afterward as a / gcd * b.

Why gcd(a, b) = gcd(b, a mod b) — the correctness core. Write a = q·b + r where r = a mod b. Take any common divisor d of a and b. Since d divides a and d divides q·b, it divides their difference a − q·b = r. So d also divides b and r — d is a common divisor of (b, r). Conversely, any common divisor of b and r divides q·b + r = a, so it's a common divisor of (a, b). The two pairs therefore have exactly the same set of common divisors, and in particular the same greatest one. Replacing (a, b) with (b, r) leaves the gcd untouched.

Why it terminates fast. The remainder r = a mod b is strictly less than b, and one can show r < a/2 whenever a swap happens across two steps. So the pair at least halves every two iterations — the number of steps is logarithmic in min(a, b). The classic worst case is consecutive Fibonacci numbers, which is exactly where the step count is largest yet still O(log).

Why the loop ends at b = 0. gcd(x, 0) = x because every integer divides 0, so the largest common divisor of x and 0 is x itself. When b reaches 0, the surviving a is the gcd.

Why LCM is a / gcd * b, in that order. From a·b = gcd·lcm we get lcm = a·b / gcd. But a·b can overflow even when lcm fits: with a = b = 10⁹, a·b = 10¹⁸ (borderline for a long) while the lcm might be far smaller. Since gcd divides a exactly, a / gcd is an exact integer, and (a / gcd)·b never exceeds the true lcm — so it stays within range whenever the answer itself does. Writing a * b / gcd instead risks overflowing on the multiply before the divide ever happens.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

a = 48, b = 18

Array state

start

48 mod 18 = 12

a ↓

[0]

b ↓

[1]

Current pointerResolved stateNot processed

Final resultgcd = 6, lcm = 48 / 6 * 18 = 8 * 18 = 144

C · Code with teaching comments

solution.javaJava

Euclidean Algorithm + LCM Identity (Optimal) — optimal

4 teaching notes

1
public long gcd(long a, long b) {
2
    // gcd is conventionally non-negative; normalise sign before reducing.
3
    a = Math.abs(a);
4
    b = Math.abs(b);
5
    // Loop until the second argument is 0 — gcd(x, 0) = x.
6
    while (b != 0) {
7
        // The remainder carries all the common-divisor information; (a,b) and (b,r)
8
        // share the same gcd.
9
        long r = a % b;
10
        a = b;
11
        b = r;
12
    }
13
    return a;
14
}
15
 
16
public long lcm(long a, long b) {
17
    if (a == 0 || b == 0) return 0;
18
    long g = gcd(a, b);
19
    return a / g * b;   // divide first to avoid overflow
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(log min(a, b)) timeO(1) spaceOpen the invariant and proofExplore the proof

The whole algorithm rests on one invariant: (a, b) and (b, a mod b) share the same common divisors. That's why you can throw away a entirely and keep only the remainder — you lose no divisibility information. For LCM, the only trap is arithmetic order: divide by the gcd first because a/gcd is guaranteed exact and keeps the product bounded.

ComplexityO(log min(a, b)) time, O(1) space — Each step replaces (a, b) with (b, a mod b); the remainder is less than half the divisor at least every two steps, so the numbers shrink geometrically. That gives O(log min(a, b)) iterations, each O(1). LCM adds one division and one multiplication.

E · Edge cases and pitfalls7a = 0, b = 5 — Loop sees b ≠ 0 once: a=5, b=0 → gcd 5; lcm returns 0 via the zero guard.Explore edge cases

Edge cases handled

a = 0, b = 5Loop sees b ≠ 0 once: a=5, b=0 → gcd 5; lcm returns 0 via the zero guard.
a = 1000000000, b = 999999999Coprime → gcd 1; lcm = a / 1 * b ≈ 10¹⁸ fits in a long because we divide first.
a = b = 66 mod 6 = 0 immediately → gcd 6; lcm = 6 / 6 * 6 = 6.

Pitfalls

Writing lcm = a * b / gcd — a*b can overflow before the division; use a / gcd * b.
Looping subtraction (a -= b) instead of a mod b — degrades to O(max/min) on lopsided inputs.
Not handling b = 0 as the stopping case — an infinite loop or a divide-by-zero.
Forgetting lcm(a, 0) = 0 and gcd(0, 0) = 0 when zeros are allowed.

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) { a = Math.abs(a); b = Math.abs(b); while (b != 0) { long r = a % b;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Overflow in lcm = a * b / gcd

a*b is formed before dividing, so it can overflow long even when the true lcm fits. Dividing first (a/gcd is exact because gcd | a) keeps every intermediate ≤ the final answer.

Explore the code comparison

Don't write this

long g = gcd(a, b);
return (a * b) / g;        // a*b overflows for large a, b

Write this instead

long g = gcd(a, b);
return a / g * b;          // exact divide first, then multiply

Subtraction instead of modulo

Replacing a with a − b one step at a time is correct but does min(a,b) work when the inputs are lopsided (e.g. gcd(10⁹, 1)). The modulo collapses all those subtractions into one step.

Explore the code comparison

Don't write this

while (a != b) {
    if (a > b) a -= b; else b -= a;
}
return a;

Write this instead

while (b != 0) {
    long r = a % b;
    a = b;
    b = r;
}
return a;

Wrong stopping condition

gcd(x, 0) = x, so the loop must stop when b reaches 0. Stopping at a == b (or never checking b) either loops forever or divides by zero on the next a % b.

Explore the code comparison

Don't write this

while a != b:
    a, b = b, a % b   # a % 0 crashes when b becomes 0
return a

Write this instead

while b != 0:
    a, b = b, a % b
return a

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Euclidean reduction by remainder; LCM via the gcd identity

Code pattern to memorize

gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

lcm(a, b) = a / gcd(a, b) * b   # divide first, then multiply

Rules to remember

1gcd(a, b) = gcd(b, a mod b); the remainder shrinks fast, so it terminates in O(log min(a, b)) steps.
2The loop ends when b becomes 0 — at that point a holds the gcd. gcd(x, 0) = x by definition.
3For LCM, write a / gcd * b, not a * b / gcd — dividing first keeps the product from overflowing.
4gcd of negatives: take absolute values first; the gcd is conventionally non-negative.
5lcm(a, 0) is 0 by convention, and gcd(0, 0) = 0 — guard these if the inputs allow zeros.

Use this pattern when

Reduce a fraction to lowest terms (divide numerator and denominator by their gcd)
Find a common period / synchronisation point (LCM of cycle lengths)
Check coprimality — gcd(a, b) == 1
Any modular-arithmetic setup needing the extended version for inverses

Choose another pattern when

You need the prime factorisation itself, not just the gcd → factorise instead
You need a modular inverse → use the *extended* Euclidean algorithm, not plain gcd
Inputs are arbitrary-precision and performance-critical → consider binary (Stein's) gcd
You only ever divide by small constants → gcd may be overkill

Interview takeaway

The Euclidean algorithm is the oldest non-trivial algorithm still in daily use: replacing (a, b) with (b, a mod b) preserves the set of common divisors while shrinking the numbers geometrically. Once you have gcd, LCM is free via a/gcd*b — and remembering to divide before multiplying is the difference between a correct answer and a silent overflow.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCanonical Euclidean reduction. Whenever a problem reduces to common divisors, fraction simplification, coprimality, or synchronisation periods, reach for gcd via (a, b) → (b, a mod b). LCM and the extended (inverse-finding) version are direct extensions.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Extended Euclidean Algorithm
Coming soon
Also return x, y with a·x + b·y = gcd(a, b) — the basis for modular inverses.
Greatest Common Divisor of Strings
Coming soon
The repeating-block length is gcd(len1, len2); same Euclidean idea on string lengths.
Find Greatest Common Divisor of Array
Coming soon
Fold gcd across the min and max of the array.
Euler's Totient Function
Counts integers coprime to n — gcd = 1 is the coprimality test it builds on.

Same pattern

←

Euler's Totient Function

Continue · Next problem

Modular Exponentiation

easyMath GeometryFrequently asked

GCD and LCM

Math & Number Theory · 14 of 36 · 8 min

Given two non-negative integers a and b, compute:

1
Their greatest common divisor gcd(a, b) — the largest integer that divides both.
2
Their least common multiple lcm(a, b) — the smallest positive integer that both divide.

Return both. Use the relationship a * b = gcd(a, b) * lcm(a, b), rearranged carefully to avoid integer overflow.

In plain English

Examples

Example 1

Input: a = 12, b = 18
Output: gcd = 6, lcm = 36
Note: Divisors of 12 and 18 share 6 as the largest; lcm = 12 / 6 * 18 = 36.

Example 2

Input: a = 7, b = 13
Output: gcd = 1, lcm = 91
Note: Both prime and distinct → coprime, so gcd = 1 and lcm = 7 * 13 = 91.

Example 3

Input: a = 0, b = 5
Output: gcd = 5, lcm = 0
Note: gcd(0, 5) = 5; lcm is 0 because 0 is a multiple of everything.

Constraints

0 ≤ a, b ≤ 10⁹ (so a*b can reach 10¹⁸ — overflow-aware ordering matters)
gcd(x, 0) = x and gcd(0, 0) = 0 by convention
lcm is 0 if either input is 0
Results are non-negative

Clarifying questions4First question: Can the inputs be zero or negative?Explore questions

Q1.Can the inputs be zero or negative?
I'll assume non-negative. gcd(x, 0) = x, gcd(0, 0) = 0, and lcm with a 0 is 0. For negatives I'd take absolute values, since gcd is conventionally non-negative.
Q2.How large can a and b be — should I worry about overflow?
Up to 10⁹, so a*b reaches 10¹⁸. That fits in a Java long but I still compute lcm as a/gcd*b to keep the intermediate small and safe.
Q3.Do you want an iterative or recursive gcd?
Either is O(log min(a, b)). Iterative avoids recursion-stack overhead and stack-depth worries; I'll show both.
Q4.Is a modular inverse needed anywhere?
Not for plain gcd/lcm. If it were, I'd switch to the extended Euclidean algorithm, which also returns the Bézout coefficients.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you know the Euclidean algorithm cold, can state why gcd(a, b) = gcd(b, a mod b), and whether you order the LCM arithmetic to avoid overflow.

Where candidates slip

Writing lcm as a * b / gcd (overflows for large a, b) instead of a / gcd * b, or looping subtraction instead of using the remainder (turning O(log) into O(max/min)).

How to stand out

Justify correctness: any common divisor of a and b also divides a mod b (and vice versa), so the common-divisor set is invariant — hence the gcd is preserved while the pair shrinks geometrically.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Common-Divisor Scan (Baseline)	`O(min(a, b))`	`O(1)`	Open with this to show you understand the definition before optimising — it makes the Euclidean speed-up land harder.	Read
2	Euclidean Algorithm + LCM Identity (Optimal)Optimal	`O(log min(a, b))`	`O(1)`	The answer they want. Say 'gcd(a, b) = gcd(b, a mod b)' and immediately note the divide-before-multiply order for LCM.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewgcd(a, b)b == 0 ?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Common-Divisor Scan (Baseline)

TimeO(min(a, b))SpaceO(1)

Open with this to show you understand the definition before optimising — it makes the Euclidean speed-up land harder.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

By definition, the gcd is the largest d that divides both a and b. What range must d live in?

2Hint 2Explore hint

Any common divisor is at most min(a, b). So scan d from min(a, b) downward and return the first d that divides both.

3Hint 3Explore hint

Once you have the gcd, the lcm is a / gcd * b. But notice the scan is linear in min(a, b) — what's a faster way to find the gcd?

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

a = 12, b = 18

d=12

18 % 12 = 6 ≠ 0

Statenot common

Final resultgcd = 6, lcm = 12 / 6 * 18 = 36

C · Code with teaching comments

Reference implementation previewpublic long gcdScan(long a, long b) { if (a == 0) return b; if (b == 0) return a; long start = Math.min(a, b); for (long d = start; d >= 1; d--) {Explore the full code

solution.javaJava

Common-Divisor Scan (Baseline) — reference

2 teaching notes

1
public long gcdScan(long a, long b) {
2
    if (a == 0) return b;
3
    if (b == 0) return a;
4
    // No common divisor can exceed the smaller input, so start the downward scan there.
5
    long start = Math.min(a, b);
6
    for (long d = start; d >= 1; d--) {
7
        // First d dividing both, scanning down, is the greatest common divisor.
8
        if (a % d == 0 && b % d == 0) {
9
            return d;
10
        }
11
    }
12
    return 1;
13
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.13 lines

D · Why it works and complexityO(min(a, b)) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(min(a, b)) time, O(1) space — We test up to min(a, b) candidate divisors, each in O(1), so O(min(a, b)) time and O(1) space.

E · Edge cases and pitfalls3Scanning upward and returning the last hit — wasteful; scanning down returns the gcd immediately.Explore edge cases

Pitfalls

Scanning upward and returning the last hit — wasteful; scanning down returns the gcd immediately.
Running this on 10⁹-scale inputs — O(min(a,b)) is far too slow.
Forgetting the a == 0 / b == 0 guards, which would make min(a, b) = 0 and skip the loop.

03.2

Approach 2 of 2 · Optimal

Euclidean Algorithm + LCM Identity (Optimal)

TimeO(log min(a, b))SpaceO(1)

The answer they want. Say 'gcd(a, b) = gcd(b, a mod b)' and immediately note the divide-before-multiply order for LCM.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Suppose d divides both a and b. Does d also divide a − b? And a mod b? If so, the common divisors of (a, b) and of (b, a mod b) are the same set.

2Hint 2Explore hint

Since the common-divisor set is unchanged, gcd(a, b) = gcd(b, a mod b). Keep replacing the pair until the second number is 0 — then the first is your gcd.

3Hint 3Explore hint

For lcm, use a * b = gcd * lcm, so lcm = a * b / gcd. To avoid overflow, divide first: a / gcd * b.

A · Core idea

Replace the pair (a, b) with (b, a mod b) repeatedly until the second entry becomes 0; the first entry is then the gcd. LCM is computed afterward as a / gcd * b.

Why the loop ends at b = 0. gcd(x, 0) = x because every integer divides 0, so the largest common divisor of x and 0 is x itself. When b reaches 0, the surviving a is the gcd.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

a = 48, b = 18

Array state

start

48 mod 18 = 12

a ↓

[0]

b ↓

[1]

Current pointerResolved stateNot processed

Final resultgcd = 6, lcm = 48 / 6 * 18 = 8 * 18 = 144

C · Code with teaching comments

solution.javaJava

Euclidean Algorithm + LCM Identity (Optimal) — optimal

4 teaching notes

1
public long gcd(long a, long b) {
2
    // gcd is conventionally non-negative; normalise sign before reducing.
3
    a = Math.abs(a);
4
    b = Math.abs(b);
5
    // Loop until the second argument is 0 — gcd(x, 0) = x.
6
    while (b != 0) {
7
        // The remainder carries all the common-divisor information; (a,b) and (b,r)
8
        // share the same gcd.
9
        long r = a % b;
10
        a = b;
11
        b = r;
12
    }
13
    return a;
14
}
15
 
16
public long lcm(long a, long b) {
17
    if (a == 0 || b == 0) return 0;
18
    long g = gcd(a, b);
19
    return a / g * b;   // divide first to avoid overflow
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(log min(a, b)) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7a = 0, b = 5 — Loop sees b ≠ 0 once: a=5, b=0 → gcd 5; lcm returns 0 via the zero guard.Explore edge cases

Edge cases handled

a = 0, b = 5Loop sees b ≠ 0 once: a=5, b=0 → gcd 5; lcm returns 0 via the zero guard.
a = 1000000000, b = 999999999Coprime → gcd 1; lcm = a / 1 * b ≈ 10¹⁸ fits in a long because we divide first.
a = b = 66 mod 6 = 0 immediately → gcd 6; lcm = 6 / 6 * 6 = 6.

Pitfalls

Writing lcm = a * b / gcd — a*b can overflow before the division; use a / gcd * b.
Looping subtraction (a -= b) instead of a mod b — degrades to O(max/min) on lopsided inputs.
Not handling b = 0 as the stopping case — an infinite loop or a divide-by-zero.
Forgetting lcm(a, 0) = 0 and gcd(0, 0) = 0 when zeros are allowed.

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) { a = Math.abs(a); b = Math.abs(b); while (b != 0) { long r = a % b;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Overflow in lcm = a * b / gcd

a*b is formed before dividing, so it can overflow long even when the true lcm fits. Dividing first (a/gcd is exact because gcd | a) keeps every intermediate ≤ the final answer.

Explore the code comparison

Don't write this

long g = gcd(a, b);
return (a * b) / g;        // a*b overflows for large a, b

Write this instead

long g = gcd(a, b);
return a / g * b;          // exact divide first, then multiply

Subtraction instead of modulo

Replacing a with a − b one step at a time is correct but does min(a,b) work when the inputs are lopsided (e.g. gcd(10⁹, 1)). The modulo collapses all those subtractions into one step.

Explore the code comparison

Don't write this

while (a != b) {
    if (a > b) a -= b; else b -= a;
}
return a;

Write this instead

while (b != 0) {
    long r = a % b;
    a = b;
    b = r;
}
return a;

Wrong stopping condition

gcd(x, 0) = x, so the loop must stop when b reaches 0. Stopping at a == b (or never checking b) either loops forever or divides by zero on the next a % b.

Explore the code comparison

Don't write this

while a != b:
    a, b = b, a % b   # a % 0 crashes when b becomes 0
return a

Write this instead

while b != 0:
    a, b = b, a % b
return a

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Euclidean reduction by remainder; LCM via the gcd identity

Code pattern to memorize

gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

lcm(a, b) = a / gcd(a, b) * b   # divide first, then multiply

Rules to remember

1gcd(a, b) = gcd(b, a mod b); the remainder shrinks fast, so it terminates in O(log min(a, b)) steps.
2The loop ends when b becomes 0 — at that point a holds the gcd. gcd(x, 0) = x by definition.
3For LCM, write a / gcd * b, not a * b / gcd — dividing first keeps the product from overflowing.
4gcd of negatives: take absolute values first; the gcd is conventionally non-negative.
5lcm(a, 0) is 0 by convention, and gcd(0, 0) = 0 — guard these if the inputs allow zeros.

Use this pattern when

Reduce a fraction to lowest terms (divide numerator and denominator by their gcd)
Find a common period / synchronisation point (LCM of cycle lengths)
Check coprimality — gcd(a, b) == 1
Any modular-arithmetic setup needing the extended version for inverses

Choose another pattern when

You need the prime factorisation itself, not just the gcd → factorise instead
You need a modular inverse → use the *extended* Euclidean algorithm, not plain gcd
Inputs are arbitrary-precision and performance-critical → consider binary (Stein's) gcd
You only ever divide by small constants → gcd may be overkill

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Extended Euclidean Algorithm
Coming soon
Also return x, y with a·x + b·y = gcd(a, b) — the basis for modular inverses.
Greatest Common Divisor of Strings
Coming soon
The repeating-block length is gcd(len1, len2); same Euclidean idea on string lengths.
Find Greatest Common Divisor of Array
Coming soon
Fold gcd across the min and max of the array.
Euler's Totient Function
Counts integers coprime to n — gcd = 1 is the coprimality test it builds on.

Same pattern

←

Euler's Totient Function

Continue · Next problem

Modular Exponentiation