IntermediateMath for DSABit Manipulation & Math
GCD with Euclid's algorithm (and LCM for free)
gcd(a, b) = gcd(b, a % b) until b is 0. It's O(log) fast, and lcm(a, b) = a × b / gcd(a, b).
The idea
Any number dividing both a and b also divides a % b (the remainder is a minus some multiple of b). So gcd(a, b) = gcd(b, a % b). The numbers shrink fast, and when the second one hits 0, the first is the answer.
Once you have the gcd, the least common multiple follows: lcm(a, b) = a / gcd(a, b) × b (divide first to keep numbers small).
Worked example
gcd(48, 18)
- gcd(48, 18) → 48 % 18 = 12 → gcd(18, 12)
- 18 % 12 = 6 → gcd(12, 6)
- 12 % 6 = 0 → gcd(6, 0) = 6. And lcm = 48 / 6 × 18 = 144.
In code (Python)
def gcd(a, b):
while b:
a, b = b, a % b
return a
def lcm(a, b):
return a // gcd(a, b) * b
# Python also has math.gcd and math.lcm.O(log(min(a, b))) steps.
How to spot it
- “largest string / number that divides both”, fractions, “every k-th and every m-th”, repeating cycles that line up.
Common mistakes
- Computing a × b before dividing in Java/C++ (overflow).
- Looping down from min(a, b) to 1: correct but O(n) instead of O(log n).
Where it comes up
Go further
Up next for you · Beginner
“Have I seen this?” is a set →