DSA problem
LCM of Two Numbers
Given two integers A and B, find their Least Common Multiple (LCM) - the smallest positive integer divisible by both.
Rather than scanning multiples, use the relationship LCM(A, B) = (A * B) / GCD(A, B). Once you have the GCD (via Euclid's algorithm), the LCM is a single multiply and divide away.
To avoid intermediate overflow, compute (A / GCD) * B instead of (A * B) / GCD, since A / GCD is exact and keeps the running value small. LCM shows up in scheduling (when do two periodic events align?), fraction addition, and synchronization intervals in concurrent systems.
Examples
Example 1
Input:
A = 12, B = 18Output:
36Explanation: 36 is the smallest number divisible by both 12 and 18. GCD(12, 18) = 6, so LCM = (12 / 6) * 18 = 36.
Constraints
- 1 <= A, B <= 10^9
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.