GCD & LCM
You've learned GCD and LCM. Now see why these numbers appear everywhere in competitive programming.
Lessons
1. Intro
The Goal
2. What GCD Means
Common divisors
3. What LCM Means
Common multiples
4. Naive GCD Method
Listing all divisors
5. The Euclidean Algorithm
Fast GCD computation
6. Euclidean Algorithm - Pseudocode
Implementation pattern
7. Why Euclidean Algorithm Works
The core idea
8. Recursive Version
Shorter code
9. Computing LCM from GCD
The formula
10. Why the LCM Formula Works
Prime factorization view
11. GCD of Multiple Numbers
Extending the algorithm
12. Quiz: GCD Basics
Knowledge check
13. Problem - Greatest Common Divisor of Strings
LeetCode 1071
14. GCD of Strings - The Idea
Length relationship
15. GCD of Strings - Algorithm
Two-step check
16. GCD of Strings - Pseudocode
Implementation
17. Simplifying Fractions
GCD application
18. Clock Synchronization Problem
LCM application
19. Problem - Nth Magical Number
LeetCode 878
20. Nth Magical Number - Counting Formula
Inclusion-exclusion principle
21. Nth Magical Number - Binary Search
Finding the answer
22. Nth Magical Number - Pseudocode
Implementation
23. Quiz: LCM and Applications
Knowledge check
24. Extended Euclidean Algorithm
Finding coefficients
25. Extended Euclidean - How It Works
Backtracking through steps
26. Coprime Numbers
When GCD equals 1
27. GCD Properties
Useful identities
28. Problem - Ugly Number III
LeetCode 1201
29. Ugly Number III - Inclusion-Exclusion
Counting with three sets
30. Ugly Number III - Binary Search
Finding the answer
31. Ugly Number III - Pseudocode
Implementation
32. Quiz: Inclusion-Exclusion
Knowledge check
33. When to Use GCD
Problem patterns
34. When to Use LCM
Problem patterns
35. GCD and Prime Factorization
The connection
36. GCD with Negative Numbers
Absolute values
37. GCD of Arrays
Folding from left
38. LCM of Arrays
Folding and overflow
39. Binary GCD Algorithm
Stein algorithm
40. Practice - Find GCD Sum
LeetCode 1979
41. Practice - Greatest Common Divisor Traversal
LeetCode 2709
42. Quiz: Advanced GCD
Knowledge check
43. Problem - Fraction Addition
Add fractions using GCD
44. Fraction Addition - Insight
Common denominator approach
45. Fraction Addition - Algorithm
Parse and compute
46. Fraction Addition - Implementation
The pseudocode
47. Section Recap
What we learned