✦ Reference Hub
Math for DSA ∑
You don't need to be a mathematician — but knowing these formulas and properties cold saves you critical minutes in an interview. Every topic here appears repeatedly in LeetCode medium/hard problems.
1. Number Theory Fundamentals
| Concept | Definition / Formula | Key Fact |
|---|---|---|
| Divisibility | a | b means b = a × k for some integer k | a | b and a | c → a | (b + c) |
| Prime | Divisible only by 1 and itself | Check up to √n only — O(√n) primality test |
| Composite | Has a factor ≤ √n | Every composite n has a prime factor ≤ √n |
| GCD | Largest number dividing both a and b | gcd(a, b) = gcd(b, a % b) — Euclidean algorithm |
| LCM | Smallest multiple of both a and b | lcm(a,b) = a × b / gcd(a,b). Divide first! |
| Coprime | gcd(a, b) = 1 | Consecutive integers are always coprime |
| Prime factorization | Every integer = product of primes | Unique (Fundamental Theorem of Arithmetic) |
| Number of divisors | If n = p1^a1 × p2^a2 × ..., count = (a1+1)(a2+1)... | Highly composite numbers have many divisors |
C++
// O(sqrt(n)) primality test bool isPrime(long long n) { if (n < 2) return false; if (n == 2 || n == 3) return true; if (n % 2 == 0 || n % 3 == 0) return false; for (long long i = 5; i * i <= n; i += 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; } // Prime factorization map<int,int> factorize(int n) { map<int,int> factors; for (int i = 2; i * i <= n; i++) while (n % i == 0) { factors[i]++; n /= i; } if (n > 1) factors[n]++; return factors; }
Java
boolean isPrime(long n) { if (n < 2) return false; if (n == 2 || n == 3) return true; if (n % 2 == 0 || n % 3 == 0) return false; for (long i = 5; i * i <= n; i += 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; }
Python
def is_prime(n): if n < 2: return False if n < 4: return True if n % 2 == 0 or n % 3 == 0: return False i = 5 while i * i <= n: if n % i == 0 or n % (i + 2) == 0: return False i += 6 return True
2. Modular Arithmetic — The Complete Rules
Why MOD = 10⁹ + 7?
It's the largest prime that fits in a 32-bit integer with room to multiply two values without overflowing a 64-bit integer (since (10⁹+6)² < 2⁶³). It's prime, enabling modular inverse via Fermat's little theorem.
| Property | Formula | Watch out for |
|---|---|---|
| Addition | (a + b) % m = ((a % m) + (b % m)) % m | Always safe |
| Subtraction | (a - b) % m = ((a % m) - (b % m) + m) % m | Add m before modding — result can be negative |
| Multiplication | (a × b) % m = ((a % m) × (b % m)) % m | Cast to long/int64 before multiplying |
| Division | (a / b) % m = (a × b⁻¹) % m | Only valid when m is prime and gcd(b, m) = 1 |
| Modular inverse | b⁻¹ = b^(m-2) mod m | Fermat's little theorem — requires m prime |
| Power | (a^n) % m = ((a % m)^n) % m | Use fast exponentiation |
⚠ Most Common Modular Arithmetic Mistakes
- Forgetting to cast to long in C++/Java:
int a = 1e9; a * aoverflows. Use(long long)a * a % MOD. - Dividing directly:
(a / b) % MOD ≠ a % MOD / b % MOD. Use modular inverse instead. - Negative results: In C++,
-1 % 7is-1, not6. Always add MOD after subtraction. - Python is safe: Python's
%always returns non-negative for positive modulus. C++/Java do not.
3. Powers of 2 — Memorize These
These appear constantly in binary search, DP, bitmask problems, and memory calculations.
| Power | Value | Approx | Where it appears |
|---|---|---|---|
2¹⁰ | 1,024 | ~10³ | 1 KB |
2¹⁶ | 65,536 | ~6.5×10⁴ | Max unsigned short |
2²⁰ | 1,048,576 | ~10⁶ | 1 MB (in bytes) |
2²³ | 8,388,608 | ~8×10⁶ | Float mantissa bits |
2³⁰ | 1,073,741,824 | ~10⁹ | Close to INT_MAX / 2 |
2³¹ − 1 | 2,147,483,647 | ~2.1×10⁹ | INT_MAX in 32-bit signed |
2³² | 4,294,967,296 | ~4.3×10⁹ | Max unsigned int |
2⁶³ − 1 | 9,223,372,036,854,775,807 | ~9.2×10¹⁸ | LONG_MAX in 64-bit signed |
4. Combinatorics
| Formula | What it counts | Example |
|---|---|---|
n! | Permutations of n distinct items | 3! = 6 orderings of {A,B,C} |
P(n,r) = n!/(n-r)! | Ordered selections of r from n | P(5,2) = 20 ordered pairs |
C(n,r) = n! / (r!(n-r)!) | Unordered selections of r from n | C(5,2) = 10 pairs |
2ⁿ | All subsets of n items | 2³ = 8 subsets of {A,B,C} |
C(n+r-1, r) | Combinations with repetition | Distribute n identical items in r bins |
n! / (n1! × n2! × ...) | Permutations with duplicates | MISSISSIPPI: 11!/(4!×4!×2!) |
Catalan(n) = C(2n,n)/(n+1) | BST shapes, valid parens, triangulations | C(0..7) = 1,1,2,5,14,42,132,429 |
Pascal's Triangle (nCr mod p)
C++
// Precompute C(n, r) mod p for all n, r <= MAXN const int MAXN = 1001, MOD = 1e9 + 7; long long C[MAXN][MAXN]; void precompute() { for (int i = 0; i < MAXN; i++) { C[i][0] = 1; for (int j = 1; j <= i; j++) C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD; } }
Java
static final int MOD = 1_000_000_007; long[][] C = new long[1001][1001]; void precompute() { for (int i = 0; i < 1001; i++) { C[i][0] = 1; for (int j = 1; j <= i; j++) C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD; } }
Python
from math import comb # Python 3.8+ comb(10, 3) # 120 # Manual Pascal's triangle MOD = 10**9 + 7 MAXN = 1001 C = [[0] * MAXN for _ in range(MAXN)] for i in range(MAXN): C[i][0] = 1 for j in range(1, i + 1): C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD
5. Series & Sequences — Closed Forms
These let you replace O(N) loops with O(1) formulas. Know them cold.
| Series | Formula | Example |
|---|---|---|
| Sum 1 to N | N(N+1)/2 | 1+2+...+100 = 5050 |
| Sum of squares | N(N+1)(2N+1)/6 | 1²+2²+...+N² |
| Sum of cubes | [N(N+1)/2]² | 1³+2³+...+N³ = (N(N+1)/2)² |
| Geometric series | a(rⁿ - 1)/(r - 1) | 1+2+4+...+2ⁿ⁻¹ = 2ⁿ - 1 |
| Harmonic series | 1 + 1/2 + 1/3 + ... + 1/N ≈ ln(N) | Appears in Sieve analysis |
| Sum of first N odds | N² | 1+3+5+...+(2N-1) = N² |
| Fibonacci (closed form) | F(n) = (φⁿ - ψⁿ)/√5 | φ = (1+√5)/2 ≈ 1.618 (golden ratio) |
6. Logarithm Properties
| Property | Formula | Use in DSA |
|---|---|---|
| Product rule | log(a × b) = log(a) + log(b) | Converting multiplication to addition |
| Quotient rule | log(a / b) = log(a) - log(b) | — |
| Power rule | log(aⁿ) = n × log(a) | Height of balanced tree with n nodes = log₂(n) |
| Change of base | log_b(a) = log(a) / log(b) | Convert between log₂ and log₁₀ |
| Binary search steps | ⌊log₂(N)⌋ + 1 | Max iterations to find in sorted array of size N |
| Tree height | ⌊log₂(N)⌋ | Height of complete binary tree with N nodes |
| Useful identity | log₂(N) ≈ log(N) / 0.301 | Convert natural log to log base 2 |
7. Important Constants & Limits
| Constant | Value | C++ | Java | Python |
|---|---|---|---|---|
| INT_MAX | 2,147,483,647 | INT_MAX | Integer.MAX_VALUE | float('inf') |
| INT_MIN | -2,147,483,648 | INT_MIN | Integer.MIN_VALUE | float('-inf') |
| LONG_MAX | 9.2 × 10¹⁸ | LLONG_MAX | Long.MAX_VALUE | N/A (arbitrary precision) |
| MOD (common) | 1,000,000,007 | 1e9 + 7 | 1_000_000_007 | 10**9 + 7 |
| MOD (alt) | 998,244,353 | 998244353 | 998244353 | 998244353 |
| √2 | ≈ 1.41421356 | sqrt(2) | Math.sqrt(2) | 2**0.5 |
| π | ≈ 3.14159265 | M_PI | Math.PI | math.pi |
8. Overflow Prevention
⚠ Overflow is silent and deadly
Overflow in C++/Java doesn't throw an error — it wraps around silently and produces wrong answers that pass some test cases. Python has arbitrary precision integers so overflow is never an issue.
| Situation | Danger | Fix |
|---|---|---|
a * b where a,b ~ 10⁹ | int overflow (max ~2.1×10⁹) | Cast: (long long)a * b |
lo + hi in binary search | int overflow when lo + hi > INT_MAX | Use lo + (hi - lo) / 2 |
n * (n-1) for n ~ 10⁵ | int overflow at n ≥ ~46,341 | Use (long long)n * (n-1) |
| LCM of large numbers | a * b overflows before dividing by gcd | Use a / gcd(a,b) * b (divide first) |
| DP accumulation over 10⁵ steps | int overflows if each step adds ~10⁴ | Use long/int64 |
| Factorial n! for n > 12 | int overflow; n=13 → 6.2×10⁹ | Use long (safe to n=20); beyond → BigInteger/Python |
9. Integer Division, Floor & Ceil
| Operation | C++ | Java | Python | Gotcha |
|---|---|---|---|---|
| Floor division | a / b (truncates toward 0) | a / b (truncates toward 0) | a // b (floors toward -∞) | C++/Java: -7/2 = -3, Python: -7//2 = -4 |
| Ceiling division | (a + b - 1) / b | (a + b - 1) / b | -(-a // b) or math.ceil(a/b) | Classic trick: ceil(a/b) = (a+b-1)/b for positive |
| Modulo negative | -7 % 3 = -1 | -7 % 3 = -1 | -7 % 3 = 2 | Python always non-negative for positive divisor |
| Round half up | (a + b/2) / b | (a + b/2) / b | round(a/b) (banker's rounding!) | Python round() uses banker's rounding (round half to even) |
⚠ Points to Remember
- In Python,
-7 // 2 = -4(floors toward negative infinity). In C++/Java,-7 / 2 = -3(truncates toward zero). This difference causes subtle bugs in modular arithmetic. - Always use integer types for bit operations. Floating-point bit manipulation is undefined behavior in C++.
- For combinatorics with large n, precompute factorials and inverse factorials mod p, then compute nCr = fact[n] * inv_fact[r] * inv_fact[n-r] % p.
- The Pigeonhole Principle: if N+1 items fit in N buckets, at least one bucket has 2 items. Useful for proving existence of duplicates.
Practice These Patterns