Loading…

easyBasicsSometimes asked

LCM of Two Numbers

Basics · 6 min

Given two positive integers a and b, return their least common multiple.

In plain English

LCM relates to GCD: `lcm(a, b) = a / gcd(a, b) * b`. Compute the GCD first, then combine.

Examples

Example 1

Input: a = 4, b = 6
Output: 12
Note: Multiples of both: 12.

Example 2

Input: a = 3, b = 5
Output: 15
Note: Coprime → product.

Example 3

Input: a = 6, b = 12
Output: 12
Note: 12 is a multiple of 6.

Constraints

1 ≤ a, b ≤ 10^6

Clarifying questions2First question: Can inputs be 0?Explore questions

Q1.Can inputs be 0?
lcm(0, x) is typically defined as 0; I'd confirm the contract.
Q2.How large are a and b?
It decides whether long is needed and why I divide first.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Use `lcm = a / gcd(a, b) * b`. Divide before multiplying to reduce overflow risk, and use `long` for the result.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you connect LCM to GCD and order the arithmetic to avoid overflow.

Where candidates slip

The `a * b / gcd` ordering that overflows on large inputs.

How to stand out

State the prime-exponent reason min+max=sum behind the identity.

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.

03.1

Approach 1 of 1 · Optimal

LCM via GCD

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

This is the standard, expected solution — lead with it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

LCM and GCD are linked by a famous identity — what is a·b in terms of them?

2Hint 2Explore hint

lcm = a / gcd(a, b) * b. Reuse the Euclidean gcd.

3Hint 3Explore hint

Divide before multiplying to avoid overflowing on a*b.

A · Core idea

The least common multiple comes straight from the GCD via the identity a · b = gcd(a, b) · lcm(a, b). Rearranged: lcm = a / gcd(a, b) * b.

Why divide before you multiply. Writing a * b / gcd first forms the full product a * b, which can overflow even when the LCM itself fits. Dividing a by the gcd first (which is exact, since gcd divides a) shrinks the operand before the multiply, keeping intermediates small. Same answer, no overflow.

Why the identity holds. Every prime appears in a·b with the sum of its exponents in a and b; the gcd takes the min exponent and the lcm takes the max, and min + max = the sum — so multiplying gcd and lcm reconstructs a·b.

Reuse Euclid. Compute the gcd with the Euclidean loop, then apply the formula. Use long for the result to be safe.

B · Visual dry run

Interactive dry run

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

a = 4, b = 6

gcd(4, 6)

Euclid → 2

Stategcd = 2

Final result12

C · Code with teaching comments

solution.javaJava

LCM via GCD — optimal

1 teaching note

1
public long lcm(int a, int b) {
2
    return (long) a / gcd(a, b) * b;
3
}
4
 
5
private int gcd(int a, int b) {
6
    while (b != 0) { int t = b; b = a % b; a = t; }
7
    return a;
8
}

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

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

The divide-before-multiply ordering is the subtle correctness/overflow detail interviewers look for.

ComplexityO(log(min(a,b))) time, O(1) space — dominated by the gcd computation, O(log(min(a,b))); the formula itself is O(1).

E · Edge cases and pitfalls5a = 3, b = 5 — Coprime → lcm is the product 15.Explore edge cases

Edge cases handled

a = 3, b = 5Coprime → lcm is the product 15.
a = 6, b = 12lcm = 12 (12 is already a multiple of 6).
a = 1, b = 7lcm = 7.

Pitfalls

Computing `a * b` first and overflowing.
Forgetting that LCM is derived from the GCD.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic long lcm(int a, int b) { return (long) a / gcd(a, b) * b; } private int gcd(int a, int 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.

Multiplying before dividing

`a * b` can overflow even when the LCM fits; dividing by gcd first (exact) keeps the operands small.

Explore the code comparison

Don't write this

long lcm = (long) a * b / gcd(a, b);   // a*b may overflow

Write this instead

long lcm = (long) a / gcd(a, b) * b;   // divide first

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

LCM from GCD

Code pattern to memorize

lcm = a / gcd(a, b) * b

Rules to remember

1lcm = a/gcd·b.
2Divide before multiply.
3Reuse Euclid for gcd.

Use this pattern when

Combining periods/cycles
Common-denominator and scheduling problems

Interview takeaway

a·b = gcd·lcm — know this identity cold.

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: LCM from GCD. Master it on small inputs and it transfers to harder problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

GCD of Two Numbers
The building block this reuses.

easyBasicsSometimes asked

LCM of Two Numbers

Basics · 6 min

Given two positive integers a and b, return their least common multiple.

In plain English

LCM relates to GCD: `lcm(a, b) = a / gcd(a, b) * b`. Compute the GCD first, then combine.

Examples

Example 1

Input: a = 4, b = 6
Output: 12
Note: Multiples of both: 12.

Example 2

Input: a = 3, b = 5
Output: 15
Note: Coprime → product.

Example 3

Input: a = 6, b = 12
Output: 12
Note: 12 is a multiple of 6.

Constraints

1 ≤ a, b ≤ 10^6

Clarifying questions2First question: Can inputs be 0?Explore questions

Q1.Can inputs be 0?
lcm(0, x) is typically defined as 0; I'd confirm the contract.
Q2.How large are a and b?
It decides whether long is needed and why I divide first.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Use `lcm = a / gcd(a, b) * b`. Divide before multiplying to reduce overflow risk, and use `long` for the result.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you connect LCM to GCD and order the arithmetic to avoid overflow.

Where candidates slip

The `a * b / gcd` ordering that overflows on large inputs.

How to stand out

State the prime-exponent reason min+max=sum behind the identity.

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.

03.1

Approach 1 of 1 · Optimal

LCM via GCD

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

This is the standard, expected solution — lead with it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

LCM and GCD are linked by a famous identity — what is a·b in terms of them?

2Hint 2Explore hint

lcm = a / gcd(a, b) * b. Reuse the Euclidean gcd.

3Hint 3Explore hint

Divide before multiplying to avoid overflowing on a*b.

A · Core idea

The least common multiple comes straight from the GCD via the identity a · b = gcd(a, b) · lcm(a, b). Rearranged: lcm = a / gcd(a, b) * b.

Reuse Euclid. Compute the gcd with the Euclidean loop, then apply the formula. Use long for the result to be safe.

B · Visual dry run

Interactive dry run

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

a = 4, b = 6

gcd(4, 6)

Euclid → 2

Stategcd = 2

Final result12

C · Code with teaching comments

solution.javaJava

LCM via GCD — optimal

1 teaching note

1
public long lcm(int a, int b) {
2
    return (long) a / gcd(a, b) * b;
3
}
4
 
5
private int gcd(int a, int b) {
6
    while (b != 0) { int t = b; b = a % b; a = t; }
7
    return a;
8
}

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

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

The divide-before-multiply ordering is the subtle correctness/overflow detail interviewers look for.

ComplexityO(log(min(a,b))) time, O(1) space — dominated by the gcd computation, O(log(min(a,b))); the formula itself is O(1).

E · Edge cases and pitfalls5a = 3, b = 5 — Coprime → lcm is the product 15.Explore edge cases

Edge cases handled

a = 3, b = 5Coprime → lcm is the product 15.
a = 6, b = 12lcm = 12 (12 is already a multiple of 6).
a = 1, b = 7lcm = 7.

Pitfalls

Computing `a * b` first and overflowing.
Forgetting that LCM is derived from the GCD.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic long lcm(int a, int b) { return (long) a / gcd(a, b) * b; } private int gcd(int a, int 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.

Multiplying before dividing

`a * b` can overflow even when the LCM fits; dividing by gcd first (exact) keeps the operands small.

Explore the code comparison

Don't write this

long lcm = (long) a * b / gcd(a, b);   // a*b may overflow

Write this instead

long lcm = (long) a / gcd(a, b) * b;   // divide first

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

LCM from GCD

Code pattern to memorize

lcm = a / gcd(a, b) * b

Rules to remember

1lcm = a/gcd·b.
2Divide before multiply.
3Reuse Euclid for gcd.

Use this pattern when

Combining periods/cycles
Common-denominator and scheduling problems

Interview takeaway

a·b = gcd·lcm — know this identity cold.

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: LCM from GCD. Master it on small inputs and it transfers to harder problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

GCD of Two Numbers
The building block this reuses.