aloalgoGCD & LCM
The Greatest Common Divisor (GCD) and Least Common Multiple (LCM) are fundamental number theory concepts that appear frequently in coding interviews. This guide covers efficient algorithms and common applications.Greatest Common Divisor (GCD)
The GCD of two numbers is the largest positive integer that divides both numbers without a remainder. For example, GCD(12, 18) = 6.Euclidean Algorithm
The Euclidean algorithm is an efficient method to compute GCD based on the principle:gcd(a, b) = gcd(b, a % b)Recursive Version
Least Common Multiple (LCM)
The LCM of two numbers is the smallest positive integer that is divisible by both numbers. LCM can be computed using GCD:GCD of Multiple Numbers
To find GCD of multiple numbers, apply GCD pairwise. The same applies to LCM.Extended Euclidean Algorithm
The extended Euclidean algorithm finds integers x and y such that:a*x + b*y = gcd(a, b). This is useful for finding modular inverses.Common Applications
- Simplifying fractions: Divide numerator and denominator by GCD
- Synchronization problems: When will two events coincide again? (LCM)
- Coprimality check: Two numbers are coprime if GCD = 1
- Modular inverse: Using extended Euclidean algorithm
Simplifying Fractions
Complexity
| Operation | Time Complexity |
|---|---|
| GCD (Euclidean) | O(log min(a, b)) |
| LCM | O(log min(a, b)) |
| GCD of n numbers | O(n * log max) |
Was this helpful?
Company
Practice
© 2026 aloalgo. All rights reserved.