Modular Arithmetic
Clock arithmetic and mod properties. You will see why mod 10^9 + 7 appears in contests and how to compute huge powers without overflow.
Lessons
1. Intro
(The Goal)
2. Clock Arithmetic
(Time wraps around 12)
3. The Mod Operator
(Remainder after division)
4. Negative Numbers
(Language differences matter)
5. Congruence Notation
(Same remainder means equal)
6. Modular Addition
(Add then mod, or mod then add)
7. Modular Multiplication
(Multiply then mod, or mod then multiply)
8. Modular Subtraction
(Watch for negative results)
9. Why Mod in Contests
(Overflow prevention)
10. Problem - Power of Two
(Check if number is power)
11. Power of Two - Insight
(Repeated division by 2)
12. Power of Two - Algorithm
(Loop until n becomes 1)
13. Power of Two - Implementation
(15 lines)
14. Quiz: Modular Basics
(Knowledge check)
15. Repeated Operations
(Take mod at each step)
16. Problem - Add Digits
(Digital root via mod 9)
17. Brute Force Approach
(Loop until single digit)
18. Add Digits - Insight
(Digital root and mod 9)
19. Add Digits - Algorithm
(O(1) formula)
20. Add Digits - Implementation
(3 lines)
21. Quiz: Modular Addition
(Knowledge check)
22. Fast Exponentiation
(Computing large powers)
23. Example - Fast Exponentiation
(Computing 2^10)
24. Modular Exponentiation Algorithm
(Binary exponentiation)
25. Problem - Pow(x, n)
(LeetCode 50)
26. Pow(x, n) - Insight
(Handle negative exponent)
27. Pow(x, n) - Algorithm
(Fast exponentiation with negatives)
28. Pow(x, n) - Implementation
(12 lines)
29. Modular Inverse
(Division in modular arithmetic)
30. Example - Modular Inverse
(Inverse of 3 mod 7)
31. Quiz: Modular Multiplication
(Knowledge check)
32. Common Moduli
(Values you see often)
33. Overflow Prevention
(Why mod is not optional)
34. Practice - Happy Number
(LeetCode 202)
35. Practice - Power of Three
(LeetCode 326)
36. Practice - Excel Sheet Column Number
(LeetCode 171)
37. Practice - Nth Digit
(LeetCode 400)
38. Quiz: Fast Exponentiation
(Knowledge check)
39. Real World Uses
(Beyond contests)
40. Common Mistakes
(What to avoid)
41. Debugging Tips
(When your mod code fails)
42. Problem - Super Pow
Modular exponentiation challenge
43. Super Pow - Insight
Break down large exponents
44. Super Pow - Algorithm
Digit by digit computation
45. Super Pow - Implementation
The pseudocode
46. Section Recap
What we learned