📘 Complete Mathematics for Programming & DSA — Ultimate

Guide
A comprehensive, programming-first roadmap covering fundamentals → intermediate → advanced
mathematics for algorithms and competitive programming. Every topic includes: theory → intuition →
formulas → implementation → optimization → pitfalls → practice problems.

📋 Table of Contents
🟢 FUNDAMENTALS (Must-Know Basics)
1. Number Systems & Types

2. Factors, Multiples & Divisibility

3. GCD & LCM (Euclidean Algorithm)
4. Prime Numbers & Properties

5. Square Roots & Perfect Powers

6. Factorial & Permutations

7. Arithmetic & Geometric Progressions

8. Floor, Ceil & Integer Division
9. Basic Combinatorics

10. Logarithms & Exponentials

🟡 INTERMEDIATE (Core Programming Math)

11. Modular Arithmetic

12. Fast Exponentiation (Binary Power)

13. Fibonacci Sequences & Variants

14. Sieve Algorithms

15. Advanced Primality Testing
16. Prime Factorization Techniques

17. Binomial Coefficients & Pascal's Triangle

18. Modular Inverse & Extended GCD

19. Euler's Totient Function

20. Linear Congruences
21. Probability & Expected Value

🔴 ADVANCED (Competition & Research Level)

22. Catalan Numbers & Applications

23. Chinese Remainder Theorem

24. Linear Recurrence Relations

25. Matrix Exponentiation

26. Advanced Bit Manipulation
27. Computational Geometry

28. Number Theoretic Transform (NTT)

29. Game Theory & Grundy Numbers

30. Multiplicative Functions

31. Quadratic Residues & Legendre Symbol

32. Continued Fractions

🎯 SPECIAL SECTIONS
33. Common Patterns & Templates
34. Optimization Techniques

35. Practice Problem Sets

36. Interview Questions

🟢 FUNDAMENTALS
1) Number Systems & Types
🎯 Core Concept Understanding different number types and their computational limits is crucial for
algorithm design and preventing overflow errors.

📚 Theory
Natural Numbers: N = {1, 2, 3, ...}
Integers: Z = {..., -2, -1, 0, 1, 2, ...}

Rational Numbers: Q = {p/q | p,q ∈ Z, q ≠ 0}

Real Numbers: R (all points on number line)

Complex Numbers: C = {a + bi | a,b ∈ R}

💾 Data Type Ranges

byte: -128 to 127 (8 bits)

short: -32,768 to 32,767 (16 bits)
int: -2,147,483,648 to 2,147,483,647 (32 bits, ~±2.1e9)
long: -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807 (64 bits, ~±9.2e18)

🔧 Key Implementation Logic

java

// Safe multiplication check

if (Long.MAX_VALUE / Math.abs(a) < Math.abs(b)) overflow = true;

// Modular multiplication
result = ((a % mod) * (b % mod)) % mod;

⚠️ Common Pitfalls
1. Integer overflow in intermediate calculations
2. Mixing signed/unsigned operations

3. Division by zero not handled

4. Precision loss in floating-point operations

2) Factors, Multiples & Divisibility

🎯 Core Concept Efficient divisibility checking and factor finding are fundamental to many algorithms.
🧮 Key Divisibility Rules

2: n & 1 == 0
3: sum of digits % 3 == 0
4: n & 3 == 0
5: n % 10 == 0 || n % 10 == 5
8: n & 7 == 0
9: digital root == 9
11: alternating sum of digits % 11 == 0

🔧 Key Implementation Logic

 java

// Count factors O(√n)

for (long i = 1; i * i <= n; i++) {
if (n % i == 0) {
count += (i * i == n) ? 1 : 2;
}
}

// Check divisibility by 11
while (n > 0) {
sum += add ? (n % 10) : -(n % 10);
add = !add;
n /= 10;
}

3) GCD & LCM (Euclidean Algorithm)

🎯 Core Concept The Euclidean algorithm is fundamental to number theory with O(log min(a,b))
complexity.

🧮 Core Formulas

gcd(a, b) = gcd(b, a mod b)

lcm(a, b) = |a × b| / gcd(a, b)
Extended GCD: ax + by = gcd(a, b)

🔧 Key Implementation Logic

java
 // Iterative GCD
while (b != 0) {
temp = a % b;
a = b;
b = temp;
}

// Binary GCD (Stein's algorithm)

while (((a | b) & 1) == 0) {
a >>= 1; b >>= 1; shift++;
}

4) Prime Numbers & Properties

🎯 Core Concept Prime detection using trial division optimized with 6k±1 pattern.
🧮 Key Properties
All primes > 3 are of form 6k±1

If n is composite, it has prime factor ≤ √n

Prime counting function: π(n) ≈ n/ln(n)

🔧 Key Implementation Logic

java

// Optimized primality test

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;
}

5) Square Roots & Perfect Powers

🎯 Core Concept Integer square roots using binary search or Newton's method.
🧮 Key Formulas
 Newton's method: x_{n+1} = (x_n + n/x_n) / 2
Binary search: left = 1, right = min(n, √(LONG_MAX))
Perfect power: n = k^p for some k > 1, p > 1

🔧 Key Implementation Logic

java

// Binary search for isqrt

while (left <= right) {
mid = left + (right - left) / 2;
if (mid * mid <= n) left = mid + 1;
else right = mid - 1;
}

// Newton's method
while (x != prev) {
prev = x;
x = (x + n / x) / 2;
}

6) Factorial & Permutations

🎯 Core Concept Factorial calculations with modular arithmetic and combinatorial applications.
🧮 Key Formulas

n! = 1 × 2 × 3 × ... × n
P(n,r) = n!/(n-r)!
Trailing zeros = ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + ...
Derangements: D(n) = (n-1)[D(n-1) + D(n-2)]

🔧 Key Implementation Logic

java
 // Factorial mod p
for (int i = 1; i <= n; i++) {
result = (result * i) % mod;
}

// Trailing zeros
for (int i = 5; i <= n; i *= 5) {
count += n / i;
}

7) Arithmetic & Geometric Progressions

🎯 Core Concept Sequence analysis for algorithmic patterns and mathematical modeling.
🧮 Key Formulas
Arithmetic Progression (AP)

nth term: a_n = a + (n-1)d

Sum: S_n = n/2 × [2a + (n-1)d] = n(first + last)/2

Geometric Progression (GP)

nth term: a_n = a × r^(n-1)

Sum: S_n = a(r^n - 1)/(r - 1) for r ≠ 1
Infinite sum: S_∞ = a/(1-r) for |r| < 1

🔧 Key Implementation Logic

java

// AP nth term and sum

nthTerm = first + (n - 1) * diff;
sum = n * (2 * first + (n - 1) * diff) / 2;

// GP nth term and sum

nthTerm = first * Math.pow(ratio, n - 1);
sum = first * (Math.pow(ratio, n) - 1) / (ratio - 1);
8) Floor, Ceil & Integer Division

🎯 Core Concept Proper handling of integer division and rounding operations.

🧮 Key Formulas

Floor: ⌊x⌋ = largest integer ≤ x

Ceil: ⌈x⌉ = smallest integer ≥ x
⌈a/b⌉ = (a + b - 1) / b (for positive integers)
⌊a/b⌋ = a / b (integer division)

🔧 Key Implementation Logic

java

// Ceiling division for positive numbers

ceil = (a + b - 1) / b;

// Floor division handling negative numbers

floor = (a - (a % b != 0 && (a < 0) ^ (b < 0) ? b : 0)) / b;

// Modulo with proper sign handling

mod = ((a % b) + b) % b;

9) Basic Combinatorics
🎯 Core Concept Counting principles and basic combinatorial identities.
🧮 Key Formulas

Combinations: C(n,r) = n! / (r! × (n-r)!)

Permutations: P(n,r) = n! / (n-r)!
Stars and bars: C(n+k-1, k-1)
Inclusion-Exclusion: |A ∪ B| = |A| + |B| - |A ∩ B|

🔧 Key Implementation Logic

java
 // nCr using precomputed factorials
nCr = (fact[n] * invFact[r] % MOD) * invFact[n - r] % MOD;

// Pascal's triangle
C[i][j] = C[i-1][j-1] + C[i-1][j];

// Inclusion-exclusion principle
result = sum_odd_subsets - sum_even_subsets;

10) Logarithms & Exponentials

🎯 Core Concept Logarithmic and exponential functions in algorithm analysis and numerical
computation.

🧮 Key Properties

log_a(xy) = log_a(x) + log_a(y)

log_a(x/y) = log_a(x) - log_a(y)
log_a(x^n) = n × log_a(x)
Change of base: log_a(x) = log_b(x) / log_b(a)

🔧 Key Implementation Logic

java

// Fast exponentiation
while (exp > 0) {
if (exp & 1) result = (result * base) % mod;
base = (base * base) % mod;
exp >>= 1;
}

// Binary logarithm (integer)

int log2 = 63 - Long.numberOfLeadingZeros(n);

🟡 INTERMEDIATE
11) Modular Arithmetic
🎯 Core Concept Essential for handling large numbers and cryptographic applications.
🧮 Key Properties

(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
a^φ(m) ≡ 1 (mod m) for gcd(a,m) = 1 (Euler's theorem)

🔧 Key Implementation Logic

java

// Safe modular operations

add = (a % mod + b % mod) % mod;
sub = ((a % mod - b % mod) + mod) % mod;
mul = (a % mod * b % mod) % mod;

12) Fast Exponentiation (Binary Power)

🎯 Core Concept Computing a^b mod m in O(log b) time using binary representation.
🧮 Algorithm

If b is even: a^b = (a^(b/2))^2

If b is odd: a^b = a × a^(b-1)

🔧 Key Implementation Logic

java

while (exp > 0) {

if (exp & 1) result = (result * base) % mod;
base = (base * base) % mod;
exp >>= 1;
}

13) Fibonacci Sequences & Variants

🎯 Core Concept Fibonacci and related sequences using matrix exponentiation and closed forms.
🧮 Key Formulas
 F(n) = F(n-1) + F(n-2)
Closed form: F(n) = (φ^n - ψ^n) / √5
Matrix form: [F(n+1), F(n)] = [F(n), F(n-1)] × [[1,1],[1,0]]

🔧 Key Implementation Logic

java

// Matrix exponentiation for F(n)

Matrix base = {{1, 1}, {1, 0}};
Matrix result = matrixPower(base, n);

// Space-optimized iterative
a = 0, b = 1;
for (int i = 2; i <= n; i++) {
c = (a + b) % mod;
a = b; b = c;
}

14) Sieve Algorithms

🎯 Core Concept Efficient prime generation and multiplicative function computation.
🧮 Algorithms
Sieve of Eratosthenes: Mark multiples of primes

Segmented Sieve: Handle large ranges

Linear Sieve: Each number marked exactly once

🔧 Key Implementation Logic

java
 // Basic sieve
for (int i = 2; i * i <= n; i++) {
if (!marked[i]) {
for (int j = i * i; j <= n; j += i) {
marked[j] = true;
}
}
}

// Linear sieve
for (int i = 2; i <= n; i++) {
if (spf[i] == 0) { // i is prime
for (int j = i; j <= n; j += i) {
if (spf[j] == 0) spf[j] = i;
}
}
}

15) Advanced Primality Testing

🎯 Core Concept Probabilistic and deterministic primality tests for large numbers.
🧮 Algorithms
Miller-Rabin: Probabilistic O(k log³ n)

AKS: Deterministic polynomial time

Fermat Test: Simple but has Carmichael numbers

🔧 Key Implementation Logic

java

// Miller-Rabin core logic

while ((d & 1) == 0) { d >>= 1; r++; }
x = modPow(a, d, n);
if (x == 1 || x == n - 1) continue;
for (int i = 0; i < r - 1; i++) {
x = (x * x) % n;
if (x == n - 1) break;
}
16) Prime Factorization Techniques
🎯 Core Concept Efficient factorization algorithms for cryptographic and number theory applications.
🧮 Algorithms
Trial Division: O(√n)
Pollard's Rho: O(n^(1/4))

Quadratic Sieve: Sub-exponential

Wheel Factorization: Skip multiples of small primes

🔧 Key Implementation Logic

java

// Pollard's Rho algorithm

x = (x * x + 1) % n;
y = (y * y + 1) % n;
y = (y * y + 1) % n;
gcd = gcd(Math.abs(x - y), n);

17) Binomial Coefficients & Pascal's Triangle

🎯 Core Concept Efficient computation of binomial coefficients with various optimizations.
🧮 Key Formulas

C(n,r) = n! / (r! × (n-r)!)

C(n,r) = C(n-1,r-1) + C(n-1,r) (Pascal's identity)
C(n,r) = C(n,n-r) (symmetry)
Lucas theorem: C(n,r) mod p = ∏ C(n_i, r_i) mod p

🔧 Key Implementation Logic

java
 // Pascal's triangle DP
for (int i = 0; i <= n; i++) {
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; j++) {
C[i][j] = (C[i-1][j-1] + C[i-1][j]) % mod;
}
}

// Optimized nCr calculation

for (int i = 0; i < r; i++) {
result = result * (n - i) / (i + 1);
}

18) Modular Inverse & Extended GCD

🎯 Core Concept Computing modular inverses using Extended Euclidean Algorithm and Fermat's Little
Theorem.

🧮 Key Formulas

ax + by = gcd(a,b) (Extended GCD)

a^(-1) ≡ a^(p-2) (mod p) for prime p (Fermat's Little Theorem)
a × a^(-1) ≡ 1 (mod m)

🔧 Key Implementation Logic

java

// Extended GCD for modular inverse

while (b != 0) {
q = a / b;
t = b; b = a % b; a = t;
t = y; y = x - q * y; x = t;
}

// Using Fermat's Little Theorem

inverse = modPow(a, mod - 2, mod);
19) Euler's Totient Function

🎯 Core Concept Counting integers coprime to n, fundamental to RSA and number theory.
🧮 Key Formulas

φ(n) = n × ∏(1 - 1/p) for all prime factors p of n

φ(p^k) = p^k - p^(k-1) = p^(k-1)(p-1) for prime p
φ(mn) = φ(m)φ(n) if gcd(m,n) = 1

🔧 Key Implementation Logic

java

// Using prime factorization

result = n;
for (int p : primeFactors) {
result = result / p * (p - 1);
}

// Sieve approach for range

for (int i = 2; i <= n; i++) {
if (phi[i] == i) { // i is prime
for (int j = i; j <= n; j += i) {
phi[j] = phi[j] / i * (i - 1);
}
}
}

20) Linear Congruences

🎯 Core Concept Solving equations of form ax ≡ b (mod m).
🧮 Theory

ax ≡ b (mod m) has solution iff gcd(a,m) divides b

If gcd(a,m) = 1, then x ≡ ba^(-1) (mod m)
General solution: x = x_0 + k(m/gcd(a,m))

🔧 Key Implementation Logic

java
 // Check solvability
gcd = gcd(a, m);
if (b % gcd != 0) return "No solution";

// Solve reduced equation

a /= gcd; b /= gcd; m /= gcd;
x = (b * modInverse(a, m)) % m;

21) Probability & Expected Value

🎯 Core Concept Basic probability theory for randomized algorithms and expected complexity analysis.
🧮 Key Formulas

P(A ∪ B) = P(A) + P(B) - P(A ∩ B)

E[X + Y] = E[X] + E[Y] (linearity)
E[XY] = E[X]E[Y] if X,Y independent
Var(X) = E[X²] - (E[X])²

🔧 Key Implementation Logic

java

// Expected value calculation

double expected = 0;
for (int outcome : outcomes) {
expected += outcome * probability[outcome];
}

// Geometric probability (expected trials until success)

expectedTrials = 1.0 / successProbability;

🔴 ADVANCED
22) Catalan Numbers & Applications
🎯 Core Concept Catalan numbers count many combinatorial structures: binary trees, parentheses,
paths.

🧮 Key Formulas
 C_n = (1/(n+1)) × C(2n,n) = C(2n,n) - C(2n,n+1)
C_n = ∑(i=0 to n-1) C_i × C_(n-1-i)
C_n = (4n-2)/(n+1) × C_(n-1)

🔧 Key Implementation Logic

java

// DP approach
catalan[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
catalan[i] += catalan[j] * catalan[i-1-j];
}
}

// Using binomial coefficient

catalan[n] = binomial(2*n, n) / (n + 1);

Applications: Binary trees, parentheses matching, polygon triangulation, stack sequences

23) Chinese Remainder Theorem

🎯 Core Concept Solving system of linear congruences with pairwise coprime moduli.
🧮 Theory

x ≡ a_1 (mod m_1)

x ≡ a_2 (mod m_2)
...
x ≡ a_k (mod m_k)

Solution: x = ∑(a_i × M_i × y_i) mod M

where M = ∏m_i, M_i = M/m_i, y_i = M_i^(-1) mod m_i

🔧 Key Implementation Logic

java
 // CRT implementation
M = 1;
for (int mod : moduli) M *= mod;

result = 0;
for (int i = 0; i < n; i++) {
Mi = M / moduli[i];
yi = modInverse(Mi, moduli[i]);
result = (result + remainders[i] * Mi * yi) % M;
}

24) Linear Recurrence Relations

🎯 Core Concept Solving recurrences of form a_n = c_1×a_(n-1) + c_2×a_(n-2) + ... + c_k×a_(n-k).
🧮 Theory

Characteristic equation: x^k = c_1×x^(k-1) + ... + c_k

Matrix form: [a_n, a_(n-1), ..., a_(n-k+1)] = [a_(n-1), ..., a_(n-k)] × T
Solution using matrix exponentiation: O(k³ log n)

🔧 Key Implementation Logic

java

// Transition matrix
T[0] = [c_1, c_2, ..., c_k];
for (int i = 1; i < k; i++) {
T[i][i-1] = 1;
}

// Matrix exponentiation
result = matrixPower(T, n - k);
answer = multiply(result, initial_vector);

25) Matrix Exponentiation

🎯 Core Concept Computing A^n efficiently in O(k³ log n) for k×k matrices.
🧮 Algorithm
 Same as fast exponentiation but with matrix multiplication
If n is even: A^n = (A^(n/2))²
If n is odd: A^n = A × A^(n-1)

🔧 Key Implementation Logic

java

// Matrix multiplication
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
result[i][j] = (result[i][j] + a[i][k] * b[k][j]) % mod;
}
}
}

// Matrix exponentiation
while (exp > 0) {
if (exp & 1) result = multiply(result, base);
base = multiply(base, base);
exp >>= 1;
}

26) Advanced Bit Manipulation

🎯 Core Concept Sophisticated bitwise operations for optimization and problem solving.
🧮 Key Techniques

Brian Kernighan: n & (n-1) removes rightmost set bit

Isolate rightmost bit: n & (-n)
Check power of 2: n && !(n & (n-1))
Swap without temp: a ^= b; b ^= a; a ^= b;
Count set bits: __builtin_popcount(n)

🔧 Key Implementation Logic

java
 // Subset enumeration
for (int mask = 0; mask < (1 << n); mask++) {
for (int subset = mask; subset > 0; subset = (subset - 1) & mask) {
// Process subset
}
}

// Gray code generation

grayCode[i] = i ^ (i >> 1);

// Find XOR of range

xorRange = (prefix[b] ^ prefix[a-1]);

27) Computational Geometry

🎯 Core Concept Geometric algorithms using coordinate geometry and vector operations.
🧮 Key Formulas

Cross product: (x1, y1) × (x2, y2) = x1*y2 - x2*y1

Distance: √((x2-x1)² + (y2-y1)²)
Area of triangle: |cross_product| / 2
Line intersection: Solve parametric equations

🔧 Key Implementation Logic

java
 // Point in polygon (ray casting)
crossings = 0;
for (edge in polygon) {
if (rayIntersectsSegment(point, edge)) crossings++;
}
inside = (crossings % 2 == 1);

// Convex hull (Graham scan)

sort(points, polarAngleComparator);
for (point : points) {
while (hull.size() > 1 && !leftTurn(hull[-2], hull[-1], point)) {
hull.pop();
}
hull.push(point);
}

28) Number Theoretic Transform (NTT)

🎯 Core Concept Fast polynomial multiplication using modular arithmetic instead of complex numbers.
🧮 Theory

NTT modulus: p = k×2^n + 1 (prime)

Primitive root: g such that g^((p-1)/2) ≡ -1 (mod p)
Transform: A[k] = ∑(a[j] × g^(jk)) mod p
Inverse: a[j] = (1/n) × ∑(A[k] × g^(-jk)) mod p

🔧 Key Implementation Logic

java
// NTT implementation
void ntt(long[] a, boolean invert) {
for (int i = 1, j = 0; i < n; i++) {
int bit = n >> 1;
for (; j & bit; bit >>= 1) j ^= bit;
j ^= bit;
if (i < j) swap(a[i], a[j]);
}

for (int len = 2; len <= n; len <<= 1) {

long wlen = modPow(g, (mod - 1) / len, mod);
if (invert) wlen = mo