Mathematical Thinking for DSA

Phase 0, Weeks 3–4

Math isn’t decoration on top of DSA — it’s the engine underneath. The engineers who solve hard problems aren’t smarter; they have a larger toolkit of mathematical patterns they recognize on sight. This document covers the patterns that appear most frequently in interview and competitive programming problems: induction, loop invariants, pigeonhole, modular arithmetic, logarithm identities, and combinatorics. You don’t need a math degree. You need these specific tools.

1. Proof by Induction

Induction is how you prove things about algorithms that involve “for all n” statements. It’s also the mechanical basis of dynamic programming correctness arguments.

Structure:

  1. Base case: Prove the statement holds for n=0 (or n=1, or whatever the smallest case is).

  2. Inductive step: Assume the statement holds for n=k (the inductive hypothesis). Prove it holds for n=k+1.

  3. Conclusion: By induction, the statement holds for all n ≥ base case.

Worked Example: Sum of 1 to n

Claim: 1 + 2 + 3 + … + n = n(n+1)/2 for all n ≥ 1.

Base case (n=1): Left side: 1. Right side: 1(2)/2 = 1. ✓

Inductive step: Assume 1 + 2 + … + k = k(k+1)/2 (inductive hypothesis). Prove for k+1:

1 + 2 + ... + k + (k+1)
= k(k+1)/2 + (k+1)           (by inductive hypothesis)
= (k+1)(k/2 + 1)
= (k+1)(k + 2)/2
= (k+1)((k+1) + 1)/2         ✓

This is exactly what we wanted to prove for n = k+1. ∎

Why this matters for DSA: Every time you claim a DP table correctly represents optimal substructure, you’re implicitly making an inductive argument. Every time you claim a greedy algorithm always picks correctly, you need induction to prove the greedy choice property. Train the reflex.

2. Loop Invariants

A loop invariant is a property that holds before the loop, after every iteration, and therefore after the loop terminates. It’s your contract with yourself about what the loop maintains.

Why invariants matter: They let you reason about loop correctness without tracing every iteration. They also make bugs obvious — when a loop doesn’t work, the invariant is usually violated.

Three things to prove about a loop invariant:

  1. Initialization: The invariant is true before the first iteration.

  2. Maintenance: If the invariant is true before iteration k, it’s true after iteration k.

  3. Termination: When the loop ends, the invariant (plus the termination condition) gives you what you wanted to prove.

Example: Binary Search Invariant

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target: return mid
        elif arr[mid] < target: lo = mid + 1
        else: hi = mid - 1
    return -1

Invariant: If target exists in arr, it must be at an index in [lo, hi].

  • Initialization: Before the loop, [lo, hi] = [0, n-1] = entire array. If target exists, it’s somewhere in there. ✓

  • Maintenance: Each iteration, we either find target, or we eliminate half the range while preserving the invariant (if arr[mid] < target, target can’t be in [lo, mid], so safely set lo = mid+1). ✓

  • Termination: Loop ends when lo > hi, meaning the range is empty. By the invariant, target doesn’t exist → return -1. ✓

Writing this invariant takes 2 minutes and makes off-by-one errors impossible to hide.

3. Pigeonhole Principle

Statement: If n+1 items are placed into n containers, at least one container holds more than one item.

Simple. Profound. It shows up in interview problems more than you’d expect.

Example applications:

  • In an array of n+1 integers all in range [1, n], at least one integer appears twice. (This is the premise of LeetCode #287 “Find the Duplicate Number.”)

  • In any group of 13 people, at least two share a birth month.

  • In a hash table with k buckets and n > k entries, at least one bucket has ≥ 2 entries. This is why collisions are unavoidable.

Pattern to recognize: When a problem says “prove there must exist…” or “show that at least one of…”, think pigeonhole.

4. Modular Arithmetic

Definition: a mod m is the remainder when a is divided by m. Written a ≡ r (mod m).

Properties you need:

(a + b) mod m = ((a mod m) + (b mod m)) mod m
(a × b) mod m = ((a mod m) × (b mod m)) mod m
(a - b) mod m = ((a mod m) - (b mod m) + m) mod m  ← the +m prevents negative results

Why competitive programming needs this constantly: Any problem involving “find the answer modulo 10⁹+7” requires you to apply mod at every addition and multiplication to prevent integer overflow. The answer after mod does NOT equal the answer before mod for division — modular inverse is needed for that.

Modular inverse: To “divide” by x mod m, you multiply by x^(m-2) mod m, provided m is prime. This comes from Fermat’s Little Theorem: x^(m-1) ≡ 1 (mod m) for prime m and gcd(x,m)=1.

Why 10⁹+7? It’s a large prime. Primes make modular inverses always exist for non-zero numbers.

Example: Compute C(100, 50) mod 10⁹+7. You need numerator and denominator both modded, then multiply by the modular inverse of the denominator.

5. Logarithm Identities

These appear in complexity analysis constantly. Memorize them.

Identity

Form

Change of base

log_a(b) = log(b) / log(a)

Product rule

log(a·b) = log(a) + log(b)

Quotient rule

log(a/b) = log(a) - log(b)

Power rule

log(a^k) = k·log(a)

Inverse

a^(log_a b) = b

Practical uses in DSA:

  • Change of base: When an algorithm halves the problem, the depth is log₂(n). When it thirds, it’s log₃(n). These differ only by a constant: log₂(n) = log₃(n) / log₃(2) = 1.585·log₃(n). For Big-O, base doesn’t matter: O(log₂n) = O(log₃n) = O(log n).

  • Why O(log n) for binary search: At each step, problem size goes n → n/2 → n/4 → … → 1. Number of steps = log₂(n).

  • Heap depth: A heap with n nodes has height ⌊log₂(n)⌋. That’s why heapify is O(log n).

  • Bit length: A number n requires ⌈log₂(n+1)⌉ bits to represent. Manipulating bits costs O(log n) per digit.

6. Combinatorics Basics

Permutations (ordered selection)

n permute k: Number of ways to choose k items from n items where order matters.

P(n, k) = n! / (n-k)! = n × (n-1) × ... × (n-k+1)

Example: How many 3-letter passwords from 26 letters (no repeats)? P(26, 3) = 26 × 25 × 24 = 15,600.

Combinations (unordered selection)

n choose k: Number of ways to choose k items from n items where order doesn’t matter.

C(n, k) = n! / (k! × (n-k)!) = P(n,k) / k!

Example: How many 5-card poker hands from 52 cards? C(52, 5) = 2,598,960.

When to use which:

  • Order matters (arrangements, sequences, passwords) → permutations

  • Order doesn’t matter (subsets, committees, combinations) → combinations

Pascal’s triangle identity: C(n, k) = C(n-1, k-1) + C(n-1, k). This is the basis for DP computation of binomial coefficients without computing factorials.

7. What Most Engineers Skip — And Why It Costs Them

Three specific LeetCode Hard problems where the math insight IS the solution:

LeetCode #1201 — Ugly Number III (Math: Inclusion-Exclusion + Binary Search) The naive approach tries every number. The math insight: use inclusion-exclusion to count numbers in [1, x] divisible by a, b, or c. Then binary search on x. Without the counting formula, you cannot make this efficient. The counting formula requires LCM, which requires GCD (Euclidean algorithm), which is number theory.

LeetCode #878 — Nth Magical Number (Math: LCM + Binary Search) Count of magical numbers ≤ x = x/a + x/b - x/lcm(a,b). Again: binary search on the answer + a counting formula derived from inclusion-exclusion. The counting formula is pure number theory.

LeetCode #829 — Consecutive Numbers Sum (Math: Arithmetic series) A number n is the sum of k consecutive integers starting at m: km + k(k-1)/2 = n. So m = (n - k(k-1)/2) / k must be a positive integer. Count valid k values. This is literally solving a Diophantine equation. There’s no “pattern” or “data structure” here — it’s math or nothing.

The pattern: if you see “count how many X satisfy property Y” and Y involves divisibility, you probably need number theory. If you see “sum of consecutive” or “arithmetic sequence,” you need the sum formula. If you see “subsets” or “arrangements,” you need combinatorics.

Return to README.md · Next: 04_pseudocode_and_invariants.md