GCD and LCM
easyTime: O(log(min(a,b)))Space: O(1)
Recognize the pattern
GCD and LCMEuclidean algorithmrepeated remainder
Brute force idea
Try all divisors — O(min(a,b)).
Better approach
gcd(a,b) = gcd(b, a%b). LCM = a / gcd × b. O(log min(a,b)).
Key invariant
Any common divisor of a and b also divides their remainder. The algorithm shrinks by at least half each step.
Watch out for
LCM overflow — compute a/gcd × b instead of a×b/gcd.