Easy · Euclidean Algorithm
Understand → Visualise → Practice.
Return `[gcd, lcm]` for two integers, using non-negative results. Define lcm as 0 if either value is 0.
gcd(a, b) = gcd(b, a mod b) until the remainder is 0. Then lcm = |a × b| / gcd, computed as |a| / gcd × |b| to keep numbers small.
Work with |a| and |b| so both results are non-negative.
Repeat (x, y) = (y, x mod y) until y = 0; x is the gcd.
If gcd is 0 (both inputs 0) or either input is 0, lcm is 0; otherwise |a| / gcd × |b|.
O(log min(a, b)) time and O(1) space.
Multiplying before dividing can overflow in fixed-width languages; divide by the GCD first.
Read the full guide first: Number Theory Basics for Algorithms.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.