Math

Type: Math / Theory

---

Core Concepts

Divisor — an integer d that divides n with no remainder; trial-division finds all divisors of n in O(√n) by iterating i up to √n and collecting both i and n//i.

Prime — a positive integer > 1 with exactly two divisors (1 and itself); all integers factor uniquely into primes (Fundamental Theorem of Arithmetic).

GCD (Greatest Common Divisor) — largest integer dividing both a and b; gcd(a,b) = gcd(b, a%b), base gcd(a,0) = a.

LCM (Least Common Multiple) — lcm(a,b) = a * b // gcd(a,b); always divide before multiplying to avoid overflow.

Modular Arithmetic — arithmetic wrapping modulo m; (a+b)%m = ((a%m)+(b%m))%m and (ab)%m = ((a%m)(b%m))%m; subtraction can go negative, so use (a - b + m) % m.

Modular Inverse — a⁻¹ mod m such that a * a⁻¹ ≡ 1 (mod m); exists iff gcd(a,m) = 1; when m is prime, inverse = a^(m−2) mod m by Fermat's little theorem.

Fermat's Little Theorem — for prime p and a not divisible by p: a^(p−1) ≡ 1 (mod p); gives modular inverse as a^(p−2) mod p.

Euler's Totient φ(n) — count of integers in [1,n] coprime to n; φ(p) = p−1 for prime p; φ(p^k) = p^(k−1)·(p−1); multiplicative for coprime factors.

Chinese Remainder Theorem (CRT) — if m₁, m₂ are coprime, there is a unique x mod (m₁·m₂) satisfying x≡a₁ (mod m₁) and x≡a₂ (mod m₂).

Combination C(n,r) — number of ways to choose r items from n: n! / (r! · (n−r)!); compute mod prime using precomputed factorials and modular inverses.

Permutation P(n,r) — ordered arrangements: n! / (n−r)!.

Stars and Bars — ways to distribute n identical items into k distinct bins allowing empty = C(n+k−1, k−1); requiring at least 1 per bin = C(n−1, k−1).

Inclusion-Exclusion — |A∪B| = |A|+|B|−|A∩B|; generalizes: alternating sum over all subsets.

Pigeonhole Principle — if n+1 items go into n bins, at least one bin holds ≥ 2; used to prove existence results and set bounds.

2D Cross Product — (b−a)×(c−a) = (bx−ax)(cy−ay) − (by−ay)(cx−ax); >0 means counter-clockwise turn, <0 means clockwise, =0 means collinear.

Integer Square Root — floor(√n); verify with isqrt(n)²≤n<(isqrt(n)+1)²; never rely on floating-point sqrt for exact checks.

Trailing zeros in n! — count factors of 5: Σ floor(n/5^k) for k=1,2,... while 5^k ≤ n; factors of 2 are always more plentiful so 5 is the bottleneck.

---

Types / Variants

---

Key Algorithms

Euclidean GCD

gcd(a,b) = gcd(b, a%b); base case gcd(a,0) = a. — O(log min(a,b)) time.

Sieve of Eratosthenes

For each prime p ≤ √n, mark p², p²+p, p²+2p, … as composite. Produces all primes ≤ n. — O(n log log n) time, O(n) space.

sieve = [True]*(n+1); sieve[0]=sieve[1]=False
for p in range(2, int(n**0.5)+1):
    if sieve[p]:
        for i in range(p*p, n+1, p): sieve[i]=False

Segmented Sieve

Sieve primes up to √R, then for range [L,R] mark composites using those primes. — O((R−L+1) log log R + √R log log √R) time, O(√R + R−L) space. Use when R is too large to allocate directly but R−L is manageable.

Smallest Prime Factor (SPF) Sieve

Run a sieve storing the smallest prime dividing each n ≤ N. Factorize any query n in O(log n) by repeatedly dividing by SPF[n]. — O(N log log N) setup, O(log n) per factorization.

Binary Exponentiation (Fast Power)

Compute a^n mod m in O(log n) by repeated squaring.

def pow_mod(a, n, m):
    res = 1; a %= m
    while n:
        if n & 1: res = res*a%m
        a = a*a%m; n >>= 1
    return res

Use Python's built-in pow(a, n, m) — it implements this and is faster in practice.

Extended Euclidean Algorithm

Finds integers x, y such that ax + by = gcd(a,b). Backbone of modular inverse when m is not prime (requires gcd(a,m)=1). — O(log min(a,b)).

Modular Inverse via Fermat's Little Theorem

inv(a, p) = pow(a, p-2, p) for prime p. — O(log p). Fails silently if p is not prime or gcd(a,p) ≠ 1.

Linear Sieve for Inverses

Precompute inv[1..n] mod prime p in O(n):

inv[1] = 1
for i in range(2, n+1):
    inv[i] = -(p//i) * inv[p%i] % p

Use over repeated Fermat calls when you need inverses for all integers up to n.

Precomputed Factorials + Modular Inverses

Build fact[0..n] and inv_fact[0..n] mod prime p in O(n) setup, then answer each C(n,r) in O(1):

C = lambda n,r: fact[n]*inv_fact[r]%p*inv_fact[n-r]%p if 0<=r<=n else 0

Pascal's Triangle

C(n,r) = C(n−1,r−1) + C(n−1,r), C(n,0)=C(n,n)=1. Build mod m in O(n²). Use when m is not prime (no Fermat inverse) and n ≤ ~2000.

Lucas' Theorem

C(n,r) mod prime p = product of C(nᵢ,rᵢ) mod p where nᵢ,rᵢ are base-p digits of n,r. Use when n > p and p is prime.

Prime Factorization (Trial Division)

Divide by 2, then by odd numbers up to √n. — O(√n) per query.

Shoelace Formula (Polygon Area)

Area = |Σᵢ (xᵢ·yᵢ₊₁ − xᵢ₊₁·yᵢ)| / 2 over vertices in order (wrapping). Use cross-product accumulation with integers; divide by 2 at the end.

Integer Square Root Verification

s = math.isqrt(n); is_perfect_square = (s*s == n). Never use int(math.sqrt(n)) — it can be off by 1 for large n.

Euler's Totient Sieve

Initialize φ[i]=i for all i, then for each prime p set φ[kp] = φ[kp]*(p−1)//p for all multiples kp. — O(N log log N). Use for aggregating totient values over all n ≤ N.

---

Advanced Techniques

Matrix Exponentiation for Linear Recurrences

When a recurrence has form v[n] = A·v[n−1] for a fixed k×k transition matrix A, compute A^n in O(k³ log n). Applies to Fibonacci (k=2), Tribonacci, any constant-depth linear recurrence. Use over iterative DP when n > 10^9 and k ≤ ~10. Space: O(k²). Don't use when k is large — k³ factor dominates.

Precomputed Factorials + Modular Inverses (for Query-Heavy Combinatorics)

After O(n) setup, each C(n,r) query costs O(1). Essential when the same modulus appears across thousands of queries. Use when p is a fixed large prime (commonly 10⁹+7 or 998244353). Don't use when m is composite — no Fermat inverse exists; fall back to Pascal's triangle or CRT.

Chinese Remainder Theorem Construction

Given x≡a₁(mod m₁), x≡a₂(mod m₂) with gcd(m₁,m₂)=1: x = a1 + m1 * ((a2-a1) * inv(m1, m2) % m2) Combine k congruences iteratively. Use when a problem decomposes into independent modular constraints with coprime moduli. Don't use when moduli are not coprime — requires generalized CRT.

Digit Counting per Position

Count numbers in [1,n] having digit d at position p by splitting n into prefix/suffix parts. Gives O(log n) per query. Use for problems like "count digit 1 in all numbers from 1 to n." Simpler than digit DP when only one digit or one property is tracked.

See dynamic-programming.md for full Digit DP coverage.

Multiplicative Function Sieve

When f(n) is multiplicative (f(ab)=f(a)f(b) for gcd(a,b)=1), compute f for all n ≤ N via SPF sieve in O(N log log N): factorize each n using SPF chain and apply the multiplicative formula. Applies to φ, σ (sum of divisors), d(n) (number of divisors). Use over per-query factorization when you need f(n) for all n ≤ N simultaneously.

---

Problem Taxonomy

By Problem Category

Problem Signal → Technique

---

Common Patterns

---

Edge Cases & Pitfalls

• gcd(0, 0): Python returns 0; gcd(a, 0) = a is correct but handle the all-zero input explicitly if 0 is a valid problem input.
• LCM overflow: a*b overflows int64 before dividing by gcd in C++/Java; always write a // gcd(a,b) * b (divide first).
• Negative modular results: Python's % always returns non-negative, but C++/Java return the sign of the dividend; use ((x % m) + m) % m when porting.
• Modular inverse requires gcd(a,m)=1: calling pow(a, p-2, p) when a is divisible by p returns 0, not an error; validate or use extended GCD.
• Floating-point sqrt off by 1: int(math.sqrt(n)) can underestimate for large perfect squares; always use math.isqrt(n).
• Sieve marking starts at p²: starting from 2p is correct but wastes time on numbers already marked; start from p*p.
• Pascal's triangle mod for composite m: nCr mod composite m cannot use Fermat's inverse; build Pascal's triangle row-by-row or use Lucas' theorem if m is a prime power.
• Digit extraction order: %10///10 gives digits least-significant first; reverse if you need most-significant first.
• Collinearity via slope: slope equality requires dividing, risking float errors and division-by-zero on vertical lines; always use integer cross product (b−a)×(c−a)==0.
• n=1 is not prime: trial division loops from 2; the sieve correctly marks index 1 as False — but manual primality checks often forget this.
• Stars and bars off-by-one: allowing empty bins → C(n+k−1, k−1); requiring ≥1 per bin → C(n−1, k−1); confusing the two is the most common combinatorics mistake.
• Cube root via float: round(n**(1/3))**3 == n can fail for very large n due to float precision; use integer binary search for exact integer cube root.
• Digit counting boundary double-count: when counting digits at each position, the boundary number n itself is often added or subtracted incorrectly at position boundaries.

---

Implementation Notes

• math.gcd(a, b) handles non-negative integers in Python; math.lcm(a, b) (Python 3.9+) handles multiple arguments.
• math.isqrt(n) is exact for all non-negative integers; always prefer it over int(math.sqrt(n)).
• pow(a, b, m) is a Python built-in using fast modular exponentiation — always use this, never (a**b) % m which computes the full value first.
• math.comb(n, r) is a built-in (Python 3.8+) returning exact C(n,r) without modulus; for modular C(n,r), precompute factorials.
• Python integers are arbitrary precision, so intermediate products do not overflow — but they become slow for huge values without modular reduction at each step.
• For geometry with integer coordinates, keep all arithmetic integer (cross products, Shoelace formula) — never convert to float mid-computation.
• The Shoelace formula gives twice the signed area as an integer; divide by 2 at the end (or use // 2 when you know it's even).
• fractions.Fraction gives exact rational arithmetic but is too slow for large competitive-style inputs; use it only for small geometric proofs or debugging.
• itertools.combinations and permutations enumerate objects — do not use them for counting when n is large; use the formula directly.

---

Cross-Topic Relations

---

Interview Reference

Must-Know Problems

Primes & Divisors

• Count Primes (LC 204) — Sieve of Eratosthenes
• Ugly Number II (LC 264) — three-pointer merge on primes 2, 3, 5
• Largest Component Size by Common Factor (LC 952) — factor-based Union-Find (hard)

GCD / LCM

• Find GCD of Array (LC 1979)
• Fraction Addition and Subtraction (LC 592) — GCD for reduction at each step
• Water and Jug Problem (LC 365) — reachable iff target is a multiple of gcd(x,y)

Modular Arithmetic & Fast Power

• Pow(x, n) (LC 50) — binary exponentiation with negative n handling
• Super Pow (LC 372) — modular exponentiation with large exponent given as array
• Count Good Numbers (LC 1922) — fast pow applied to position-based counting

Combinatorics

• Pascal's Triangle I & II (LC 118, 119)
• Unique Paths (LC 62) — C(m+n−2, m−1)
• K-th Smallest in Lexicographic Order (LC 440) — digit counting to find subtree sizes (hard)

Geometry

• Max Points on a Line (LC 149) — slope as GCD-reduced fraction; handle vertical and identical points
• Rectangle Area (LC 223) — inclusion-exclusion on two rectangles
• Erect the Fence (LC 587) — convex hull via Andrew's monotone chain (hard)

Digit Problems

• Number of Digit One (LC 233) — digit counting formula per position
• Self Dividing Numbers (LC 728) — digit extraction and divisibility check
• Happy Number (LC 202) — cycle detection on digit-square-sum iteration

Sequence / Recurrence

• Fibonacci Number (LC 509) — base problem; try matrix exponentiation as follow-up
• Climbing Stairs (LC 70) — Fibonacci variant
• Nth Digit (LC 400) — arithmetic to find the digit's range, position, and offset

Additional LeetCode Coverage

• Check If It Is a Straight Line (LC 1232)
• Find Numbers with Even Number of Digits (LC 1295)
• The kth Factor of n (LC 1492)
• Count Odd Numbers in an Interval Range (LC 1523)
• Sign of the Product of an Array (LC 1822)
• Factorial Trailing Zeroes (LC 172)

Clarification Questions to Ask

• Is the modulus always prime? (Determines if Fermat's little theorem gives the inverse)
• Can n be 0 or 1? (Edge cases for primality, factorization, totient)
• Are coordinates guaranteed to be integers? (Determines if integer geometry is safe)
• Should the answer count ordered or unordered pairs? (Affects divisibility by 2 or permutation factor)
• What is the constraint on n? (Determines sieve vs. trial division vs. SPF sieve)
• Is "path" here Euclidean distance or Manhattan distance? (Geometry problems)

Common Interview Mistakes

• Using int(math.sqrt(n)) instead of math.isqrt(n), causing off-by-one failures on large perfect squares.
• Writing a*b // gcd(a,b) for LCM instead of a // gcd(a,b) * b, causing overflow in fixed-width integer languages.
• Calling pow(a, p-2, p) when a is divisible by p, silently producing 0 instead of raising an error.
• Using floating-point slope for collinearity instead of the integer cross product, hitting division-by-zero on vertical lines.
• Forgetting n=1 is not prime in manual trial-division checks.
• Applying %m only at the very end of a long product chain, causing intermediate value explosion.
• Off-by-one in digit counting — forgetting the boundary number or double-counting it.
• Confusing "arrangements" (permutations, order matters) with "selections" (combinations, order doesn't matter).
• Stars and bars off-by-one: using C(n+k−1,k−1) when the problem requires at least one per bin (should be C(n−1,k−1)).

Typical Follow-Up Escalations

• "Now solve it for range [L, R]" → segmented sieve or prefix-sum over precomputed arrays
• "n can be up to 10^18" → matrix exponentiation for recurrences; Miller-Rabin primality for individual values
• "Output mod 10^9+7" → add factorial precomputation and modular inverse on top of the existing solution
• "Now count coprime pairs in array" → Euler's totient + Möbius inclusion-exclusion over prime factors
• "What if the modulus is not prime?" → switch from Fermat inverse to extended Euclidean or row-by-row Pascal's triangle