Algoritms Set

Bitwise XOR (^)

Exclusive OR operation. Returns 1 if bits differ, 0 if same. Example: 5 ^ 3 = 6 (101 ^ 011 = 110). Use cases: swap variables without temp, find unique element, toggle bits, checksums.

Big O Notation

Describes algorithm time/space complexity. O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) linearithmic, O(n²) quadratic, O(2ⁿ) exponential. Ignores constants and lower terms.

Amortized Analysis

Average time per operation over worst-case sequence. Example: Dynamic array append is O(1) amortized even though resize is O(n), because resize happens rarely.

Combinatorics - Permutations

Number of ways to arrange n items: n! (n factorial). For r items from n: P(n,r) = n!/(n-r)!. Example: 5P3 = 5×4×3 = 60 ways to arrange 3 items from 5.

Combinatorics - Combinations

Number of ways to choose r items from n (order doesn't matter): C(n,r) = n!/(r!(n-r)!). Example: C(5,2) = 10 ways to choose 2 items from 5.

Pigeonhole Principle

If n items are placed into m containers and n > m, at least one container must contain more than one item. Used to prove collision/duplicate existence.

Euclidean Algorithm

Efficient method to find GCD. gcd(a,b) = gcd(b, a mod b), base case when b=0. Example: gcd(48,18) → gcd(18,12) → gcd(12,6) → gcd(6,0) = 6.

Modular Arithmetic

Math with wraparound at modulus m. (a + b) mod m = ((a mod m) + (b mod m)) mod m. Useful for: hash functions, cryptography, circular buffers, time calculations.

Modular Exponentiation

Computing (base^exp) mod m efficiently for large numbers. Uses repeated squaring to avoid overflow. Essential for RSA encryption and competitive programming.

Chinese Remainder Theorem

System of congruences with coprime moduli has unique solution mod (product of moduli). Used in: distributed computing, calendar calculations, number theory problems.

Bit Manipulation - Count Set Bits

Brian Kernighan's algorithm: while(n) { n &= (n-1); count++; } removes rightmost 1-bit each iteration. Or use __builtin_popcount() in C++.

Bit Manipulation - Power of 2 Check

n > 0 && (n & (n-1)) == 0. Powers of 2 have exactly one bit set. Example: 8 = 1000, 8-1 = 0111, 8 & 7 = 0.

Bit Masks

Use integers to represent sets. Set bit: mask |= (1 << i). Clear bit: mask &= ~(1 << i). Toggle bit: mask ^= (1 << i). Check bit: (mask & (1 << i)) != 0.

Two's Complement

Negative number representation: flip all bits and add 1. -n = ~n + 1. Example: -5 in 8-bit = ~00000101 + 1 = 11111011. Allows same circuitry for add/subtract.

Fast Inverse Square Root

Famous Quake III algorithm: combines bit manipulation, Newton-Raphson, and magic constant 0x5f3759df. Approximates 1/√x incredibly fast for 3D graphics.

Prefix Sum (Cumulative Sum)

Precompute sums from start: prefix[i] = arr[0] + ... + arr[i]. Range sum [L,R] = prefix[R] - prefix[L-1] in O(1). Trades space for query speed.

Sliding Window Maximum

Find max in all k-sized windows. Use deque maintaining decreasing elements. O(n) time vs O(n*k) naive. Essential for many array optimization problems.

Binary Search on Answer

When answer space is monotonic, binary search the solution rather than computing directly. Example: minimize maximum, capacity problems, finding kth element.

Monotonic Stack

Stack maintaining elements in increasing/decreasing order. Used for: next greater element, histogram max area, stock span. Process each element once = O(n).

Sieve of Eratosthenes

Find all primes ≤ n. Mark multiples of each prime starting from prime². Time: O(n log log n). Space: O(n). Most efficient for generating many primes.

Prime Factorization

Every integer > 1 has unique prime factorization. Trial division up to √n finds all factors. Used in: GCD, LCM, counting divisors, cryptography.

Exponent Laws

a^m × a^n = a^(m+n), (a^m)^n = a^(mn), a^m / a^n = a^(m-n), a^0 = 1, a^(-n) = 1/a^n. Critical for simplifying expressions and complexity analysis.

Logarithm Laws

log(xy) = log(x) + log(y), log(x/y) = log(x) - log(y), log(x^n) = n×log(x), log_b(x) = log(x)/log(b). Change of base formula essential for conversions.

Matrix Exponentiation

Compute A^n in O(k³ log n) for k×k matrix using repeated squaring. Solves linear recurrences (Fibonacci) in logarithmic time. Also used in graph problems.

Fibonacci - Closed Form

F(n) = (φⁿ - ψⁿ)/√5 where φ=(1+√5)/2 (golden ratio), ψ=(1-√5)/2. Binet's formula gives exact Fibonacci in O(1) but limited by float precision.

Catalan Numbers

C_n = (2n)!/(n!(n+1)!) = C(2n,n)/(n+1). Counts: valid parentheses, binary trees, paths not crossing diagonal. Recurrence: C_n = Σ C_i × C_(n-1-i).

Geometric Series Sum

a + ar + ar² + ... + ar^(n-1) = a(1-r^n)/(1-r). Infinite series (|r|<1): a/(1-r). Used in complexity analysis, probability, financial calculations.

Arithmetic Series Sum

Sum of first n terms: S_n = n(a_1 + a_n)/2 = n(2a_1 + (n-1)d)/2. Sum 1 to n: n(n+1)/2. Used constantly in loop analysis.

Expected Value

E[X] = Σ x_i × P(x_i). Average outcome weighted by probability. Linearity: E[X+Y] = E[X] + E[Y] even if dependent. Essential for probabilistic algorithms.

Inclusion-Exclusion Principle

|A∪B| = |A| + |B| - |A∩B|. For n sets: alternate adding/subtracting intersection sizes. Counts elements in at least one set, avoiding double-counting.

Convex Hull

Smallest convex polygon containing all points. Algorithms: Graham scan O(n log n), Jarvis march O(nh). Used in: computational geometry, image processing, collision detection.

Kadane's Algorithm

Find maximum sum subarray in O(n). Track max_ending_here = max(arr[i], max_ending_here + arr[i]). Classic dynamic programming example.

Union-Find Path Compression

Disjoint set with path compression + union by rank achieves nearly O(1) operations (inverse Ackermann). Essential for: Kruskal's MST, cycle detection, dynamic connectivity.

Euler's Totient Function

φ(n) counts integers ≤ n coprime to n. For prime p: φ(p) = p-1. Formula: φ(n) = n × ∏(1 - 1/p) for prime factors p. Used in RSA, number theory.

Fast Fourier Transform (FFT)

Computes DFT in O(n log n) vs O(n²). Multiplies large polynomials efficiently. Applications: signal processing, image compression, big integer multiplication.

Gray Code

Binary sequence where consecutive values differ by exactly one bit. Formula: G(n) = n XOR (n >> 1). Used in: error correction, genetic algorithms, puzzle solving.

Meet in the Middle

Split search space in half, solve both halves separately, combine results. Reduces O(2ⁿ) to O(2^(n/2)). Used in subset sum, cryptanalysis.

Z-Algorithm

Finds all occurrences of pattern in text in O(n+m). Computes Z-array where Z[i] = longest substring starting at i matching prefix. Alternative to KMP.

Coordinate Compression

Map sparse coordinates to dense range [0, k-1]. Sort unique values, replace with indices. Reduces space from O(max_value) to O(unique_values).

Difference Array

For range updates: diff[L]++, diff[R+1]--. Prefix sum recovers values. Turns O(n) range update to O(1). Multiple updates then one O(n) reconstruction.

Ternary Search

Find max/min of unimodal function. Divide into 3 parts, eliminate 1/3 each step. Complexity: O(log₃ n). Used for optimization problems with single peak/valley.

Manacher's Algorithm

Find longest palindromic substring in O(n). Clever use of symmetry to avoid re-checking. Fastest known algorithm for this problem.

Rolling Hash (Rabin-Karp)

Hash substring using polynomial rolling hash. Update hash in O(1) when sliding window. Formula: hash = (hash - arr[i]×p^(k-1)) × p + arr[i+k]. Used in pattern matching.