All Topics
Math & Number Theory
GCD, primes, modular arithmetic, combinatorics, and mathematical patterns
0/40 solved
GCD, LCM & Euclidean
Greatest Common Divisor and Least Common Multiple using Euclid's algorithm
O(log(min(a,b))) O(1)
Approach
Use Euclidean algorithm for GCD in O(log(min(a,b))). Derive LCM from GCD. For problems involving multiple numbers, apply GCD/LCM iteratively.
How to Recognize
1
Need GCD or LCM of numbers
2
Reducing fractions to lowest terms
3
Phrases like 'greatest common divisor', 'water jug problem'
4
Problems involving divisibility of multiple numbers
Pro Tips
Euclidean algorithm: gcd(a,b) = gcd(b, a%b), base case gcd(a,0) = a
LCM(a,b) = a * b / GCD(a,b)
Extended Euclidean gives x,y such that ax + by = gcd(a,b)
8
Total
4
Easy
3
Medium
1
Hard
Time
O(log(min(a,b)))
Space
O(1)