Foundations
Modular arithmetic
Mod, congruences, inverses, Fermat - underpins hashing and prefix-mod DP.
Question: how many subarrays of a 23-element array sum to a multiple of 5?
Naive O(n²) walks 530 pairs. But look at the remainders mod 5 and you drop to O(n). This page unpacks where modular arithmetic shows up, from hash buckets to prefix-mod DP.
By the numbers: mod is a clock
(a + b) mod m advances the result on a clock face. For m = 12, 10 + 5 = 3 (5 hours past midnight). mod m always lands in 0..m-1. Spin the clock and watch how the result wraps.
Properties (quick recall for interviews):
(a + b) mod m = ((a mod m) + (b mod m)) mod m(a · b) mod m = ((a mod m) · (b mod m)) mod ma ≡ b (mod m)iffm | (a - b)
Derivation: counting subarrays with prefix-mod
Goal: count subarrays whose sum is divisible by K. Defineprefix[i] = nums[0] + … + nums[i-1]. A subarray [l, r] sums toprefix[r+1] - prefix[l]. That's divisible by K iff(prefix[r+1] - prefix[l]) mod K == 0, i.e.prefix[r+1] ≡ prefix[l] (mod K).
So: count prefixes that share the same remainder. count[r] = how many earlier prefixes have the same remainder as prefix[r]. Keep a hash map of remainder frequencies, sum them up → O(n).
Example: nums = [4, 5, 0, -2, -3, 1], K = 5. Prefix mods 5:0, 4, 4, 4, 2, 4, 0. Pairs with same remainder: (0,0) and several (4,4) → total 7. That's LC 974's solution.
Trap: "mod handles negative numbers correctly"
Watch out: -7 mod 5 gives 3 in Python but -7 % 5 = -2 in C# / TypeScript. Normalize negative remainders to positive:((x % K) + K) % K. This is a classic bug in prefix-mod DP; with negative numbers you group remainders wrong and miss subarrays.
Where to go next
- LC 523 Continuous Subarray Sum - prefix-mod with a length ≥ 2 constraint.
- LC 974 Subarray Sums Divisible by K - the example above.
- LC 560 Subarray Sum Equals K - same prefix idea, hash instead of mod.
- hashing pattern - the hash map you use to count remainders.
Exercise
Set the clock to a = 8, b = 9, m = 12. Predict the result (17 mod 12). Now change to m = 5. This shows why mod isn't just "division remainder" but wrapping a number around a ring, and why that's the move for counting problems.