Essential Math for Leet Code Problems

leet-math-cheat-sheet.md

LeetCode Math Cheat Sheet

Number Theory

Prime Numbers & Primality Tests

• Prime Number: Integer > 1 with exactly two factors (1 and itself)
• Prime Factorization: Expressing a number as product of primes
• Primality Test (naive): Check if any number from 2 to $\sqrt{n}$ divides n

function isPrime(n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 === 0 || n % 3 === 0) return false;
    for (let i = 5; i * i <= n; i += 6) {
        if (n % i === 0 || n % (i + 2) === 0) return false;
    }
    return true;
}

• Sieve of Eratosthenes: Efficient way to find all primes up to n

GCD/LCM

• GCD: Greatest Common Divisor
• LCM: Least Common Multiple
• Euclidean Algorithm for GCD:

function gcd(a, b) {
    return b === 0 ? a : gcd(b, a % b);
}

• LCM Formula: $\text{LCM}(a,b) = \frac{a \times b}{\text{GCD}(a,b)}$

Modular Arithmetic

• $(a + b) \bmod m = ((a \bmod m) + (b \bmod m)) \bmod m$
• $(a \times b) \bmod m = ((a \bmod m) \times (b \bmod m)) \bmod m$
• $(a - b) \bmod m = ((a \bmod m) - (b \bmod m) + m) \bmod m$
• Fast Modular Exponentiation:

function modPow(base, exponent, modulus) {
    if (modulus === 1) return 0;
    let result = 1;
    base = base % modulus;
    while (exponent > 0) {
        if (exponent % 2 === 1)
            result = (result * base) % modulus;
        exponent = exponent >> 1;
        base = (base * base) % modulus;
    }
    return result;
}

Base Conversion

• Decimal to Binary:

function decimalToBinary(n) {
    return n.toString(2);
}

• Binary to Decimal:

function binaryToDecimal(binary) {
    return parseInt(binary, 2);
}

• Division method: Repeatedly divide by 2, read remainders bottom-up

Floating Point

• IEEE 754 standard: sign bit, exponent, mantissa
• Limited precision: use epsilon for comparisons
• Floating Point Issues:
  • Rounding errors in arithmetic operations
  • Equality comparisons should use tolerance: $|a - b| < \epsilon$

Combinatorics & Probability

Permutations & Combinations

• Permutation: Order matters
  • $P(n,r) = \frac{n!}{(n-r)!}$
• Combination: Order doesn't matter
  • $C(n,r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}$
• Combinations with repetition: $C(n+r-1, r)$

Basic Probability

• $P(\text{event}) = \frac{\text{favorable outcomes}}{\text{total possible outcomes}}$
• Independent events: $P(A \text{ and } B) = P(A) \times P(B)$
• Mutually exclusive: $P(A \text{ or } B) = P(A) + P(B)$
• Not mutually exclusive: $P(A \text{ or } B) = P(A) + P(B) - P(A \text{ and } B)$

Bayes' Theorem

• $P(A|B) = \frac{P(B|A) \times P(A)}{P(B)}$
• Useful for updating probabilities based on new evidence

Expected Value

• $E[X] = \sum(x \times P(X = x))$
• $E[aX + b] = a \times E[X] + b$

Bit Manipulation

Bitwise Operations

• AND (&): 1 if both bits are 1
• OR (|): 1 if at least one bit is 1
• XOR (^): 1 if bits are different
• NOT (~): Flips all bits
• Left Shift (<<): Multiplies by $2^{\text{shift}}$
• Right Shift (>>): Divides by $2^{\text{shift}}$

Bit Tricks

• Check if bit is set: (num & (1 << pos)) != 0
• Set a bit: num |= (1 << pos)
• Clear a bit: num &= ~(1 << pos)
• Toggle a bit: num ^= (1 << pos)
• Check if power of 2: n > 0 && (n & (n-1)) == 0
• Count set bits:

function countSetBits(n) {
    let count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

Algebra & Functions

Logarithms & Exponentials

• Log properties:
  • $\log(a \times b) = \log(a) + \log(b)$
  • $\log(a/b) = \log(a) - \log(b)$
  • $\log(a^n) = n \times \log(a)$
• Base conversion: $\log_a(x) = \frac{\log_b(x)}{\log_b(a)}$
• Common complexity classes: $O(1)$, $O(\log n)$, $O(n)$, $O(n \log n)$, $O(n^2)$, $O(2^n)$

Polynomials & Sequences

• Arithmetic Sequence: $a_n = a_1 + (n-1)d$
  • Sum: $S_n = \frac{n}{2} \times (2a_1 + (n-1)d) = \frac{n}{2} \times (a_1 + a_n)$
• Geometric Sequence: $a_n = a_1 \times r^{n-1}$
  • Sum: $S_n = a_1 \times \frac{1 - r^n}{1 - r} \text{ for } r \neq 1$
• Fibonacci: $F(n) = F(n-1) + F(n-2) \text{ with } F(0) = 0, F(1) = 1$

Recurrence Relations

• Solve using characteristic equation or master theorem
• Master Theorem: For $T(n) = aT(n/b) + f(n)$
  • If $f(n) = O(n^c) \text{ where } c &lt; \log_b(a)$: $T(n) = \Theta(n^{\log_b(a)})$
  • If $f(n) = \Theta(n^c) \text{ where } c = \log_b(a)$: $T(n) = \Theta(n^c \log n)$
  • If $f(n) = \Omega(n^c) \text{ where } c &gt; \log_b(a)$: $T(n) = \Theta(f(n))$

Statistics

Measures of Central Tendency

• Mean: Sum of values / Count
• Median: Middle value (or average of two middle values)
• Mode: Most frequent value

Dispersion

• Range: Max - Min
• Variance: $\sigma^2 = \frac{\sum(x - \mu)^2}{n}$
• Standard Deviation: $\sigma = \sqrt{\text{Variance}}$

Percentiles & Quantiles

• k-th percentile: Value below which k% of observations fall
• Quartiles: Q1 (25%), Q2 (50% = median), Q3 (75%)
• Interquartile Range (IQR): Q3 - Q1

Sampling

• Simple Random Sampling: Each item has equal probability
• Reservoir Sampling: Algorithm for sampling k items from stream of unknown size:

function reservoirSample(stream, k) {
    let reservoir = stream.slice(0, k);
    for (let i = k; i < stream.length; i++) {
        const j = Math.floor(Math.random() * (i + 1));
        if (j < k) reservoir[j] = stream[i];
    }
    return reservoir;
}

Covariance & Correlation

• Covariance: Measure of joint variability between two variables
  • $\text{Cov}(X,Y) = \frac{\sum((x - \mu_x)(y - \mu_y))}{n}$
• Correlation: Normalized covariance (-1 to 1)
  • $\text{Corr}(X,Y) = \frac{\text{Cov}(X,Y)}{\sigma_x \times \sigma_y}$

Graph Theory

Basic Concepts

• Graph: $G = (V, E)$ where V is set of vertices and E is set of edges
• Directed vs. Undirected
• Weighted vs. Unweighted
• Adjacency Matrix: $O(V^2)$ space, $O(1)$ edge lookup
• Adjacency List: $O(V+E)$ space, $O(\text{degree}(v))$ edge lookup

Graph Traversals

• BFS: Level by level, uses queue

function bfs(graph, start) {
    const visited = new Set([start]);
    const queue = [start];
    while (queue.length > 0) {
        const node = queue.shift();
        for (let neighbor of graph[node]) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
}

• DFS: Explores as far as possible, uses stack/recursion

function dfs(graph, node, visited = new Set()) {
    visited.add(node);
    for (let neighbor of graph[node]) {
        if (!visited.has(neighbor)) {
            dfs(graph, neighbor, visited);
        }
    }
}

Shortest Path Algorithms

• Dijkstra: Single source, non-negative weights, $O(V^2)$ or $O(E \log V)$
• Bellman-Ford: Single source, handles negative weights, $O(VE)$
• Floyd-Warshall: All pairs shortest path, $O(V^3)$

Minimum Spanning Tree

• Prim's Algorithm: Start from arbitrary vertex, greedily add cheapest edge
• Kruskal's Algorithm: Sort edges by weight, add if doesn't create cycle

Topological Sort

• Only for directed acyclic graphs (DAGs)
• DFS-based approach:

function topologicalSort(graph) {
    const visited = new Set();
    const stack = [];
    
    function dfs(node) {
        visited.add(node);
        for (let neighbor of graph[node]) {
            if (!visited.has(neighbor)) {
                dfs(neighbor);
            }
        }
        stack.push(node);
    }
    
    for (let node in graph) {
        if (!visited.has(node)) {
            dfs(node);
        }
    }
    
    return stack.reverse();
}

Geometry

Coordinate Geometry

• Distance between points: $d = \sqrt{(x_2-x_1)^2 + (y_2-y_1)^2}$
• Slope of line: $m = \frac{y_2-y_1}{x_2-x_1}$
• Line equation: $y = mx + b$
• Midpoint: $(\frac{x_1+x_2}{2}, \frac{y_1+y_2}{2})$

Areas & Volumes

• Triangle Area:
  • Using base and height: $A = \frac{1}{2} \times \text{base} \times \text{height}$
  • Using coordinates (Shoelace formula):

$$A = \frac{1}{2}\left|\sum_{i=1}^{n} (x_i \times y_{i+1} - x_{i+1} \times y_i)\right|$$

• Polygon Area:
  • Triangulate, or use Shoelace formula for simple polygons
• Circle: Area = $\pi r^2$, Circumference = $2\pi r$

Line Intersections

• Line segment intersection: Determine if bounding boxes overlap, then check orientation
• Point in polygon: Ray casting algorithm or winding number algorithm

Discrete Mathematics

Set Theory

• Operations: Union ($\cup$), Intersection ($\cap$), Difference ($\setminus$), Complement ($'$)
• Properties:
  • $A \cup B = B \cup A$
  • $A \cap B = B \cap A$
  • $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
  • $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$

Logic

• Operators: AND ($\wedge$), OR ($\vee$), NOT ($\neg$), IMPLIES ($\rightarrow$), EQUIVALENT ($\leftrightarrow$)
• De Morgan's Laws:
  • $\neg(A \wedge B) = \neg A \vee \neg B$
  • $\neg(A \vee B) = \neg A \wedge \neg B$

Mathematical Induction

1. Base case: Prove for n = 1
2. Inductive step: Assume true for n = k, prove for n = k+1

Pigeonhole Principle

• If n items are put into m containers with n > m, at least one container has more than one item

Game Theory

• Nim Game: XOR all pile sizes; winning position has XOR = 0
• Minimax Algorithm: Maximize your minimum gain / minimize opponent's maximum gain