GCD and LCM
easyTime: O(log(min(a,b)))Space: O(1)
Signals to notice
GCD and LCMEuclidean algorithmrepeated remainder
Brute force first
Try all divisors — O(min(a,b)).
The key insight
gcd(a,b) = gcd(b, a%b). LCM = a / gcd × b. O(log min(a,b)).
What must stay true
Any common divisor of a and b also divides their remainder. The algorithm shrinks by at least half each step.
Easy way to go wrong
LCM overflow — compute a/gcd × b instead of a×b/gcd.