Algorithm, principles and misc concepts

Bitwise XOR (^)

Returns 1 if bits differ, 0 if same. Ex: 5^3=6 (101^011=110). Uses: Swapping variables, finding the unique element in a pair-heavy array, toggling bits.

Big O Notation

Describes asymptotic time/space complexity. O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ). Ignores constants and lower-order terms.

Amortized Analysis

The average time per operation over a worst-case sequence. Ex: Dynamic array append is O(1) amortized because O(n) resizing happens rarely.

Permutations (P)

Number of ways to arrange r items from n where order matters: $P(n,r) = \frac{n!}{(n-r)!}$. For all n items, it is simply n!.

Combinations (C)

Number of ways to choose r items from n where order doesn't matter: $C(n,r) = \frac{n!}{r!(n-r)!}$. Also called 'n choose r.'

Pigeonhole Principle

If n items are put into m containers and n > m, at least one container has >1 item. Used to prove collisions (e.g., hash overlaps).

Euclidean Algorithm

Efficient GCD method: gcd(a, b) = gcd(b, a mod b). Base case: gcd(a, 0) = a.

Modular Arithmetic

Math with 'wraparound' at modulus m. Property: (a + b) % m = ((a % m) + (b % m)) % m. Essential for preventing integer overflow.

Modular Exponentiation

Computing $(base^{exp}) \pmod m$ in O(log exp) time using repeated squaring. Prevents massive intermediate numbers.

Brian Kernighan's Algorithm

Counts set bits in an integer: while(n) { n &= (n-1); count++; }. Each step clears the least significant set bit.

Power of 2 Check (Bitwise)

A number n is a power of 2 if: (n > 0) && ((n & (n - 1)) == 0).

Bit Masks

Using bits to represent a set. Set: mask | (1 << i); Clear: mask & ~(1 << i); Toggle: mask ^ (1 << i); Check: mask & (1 << i).

Two's Complement

Standard for negative numbers: Flip all bits and add 1. Allows addition and subtraction to use the same CPU logic.

Prefix Sum Array

Precomputes cumulative sums. prefix[i] = arr[0...i]. Query range sum [L, R] in O(1) time via prefix[R] - prefix[L-1].

Sliding Window Maximum

Finds the maximum in all subarrays of size k. Solved in O(n) using a Deque to store indices in decreasing order of values.

Binary Search on Answer

Used when the search space is monotonic. Instead of calculating the result, guess a value and check if it's 'feasible.'

Monotonic Stack

A stack that keeps elements in increasing/decreasing order. Used for 'Next Greater Element' problems in O(n).

Sieve of Eratosthenes

Finds all primes up to n in O(n log log n). Iteratively marks multiples of each prime as composite.

Euler's Totient Function (phi)

$\phi(n)$ counts integers $\le n$ that are coprime to n. For prime p, $\phi(p) = p - 1$. Used in RSA encryption.

Matrix Exponentiation

Solves linear recurrences (like Fibonacci) in O(log n) by raising a transformation matrix to the power of n.

Catalan Numbers

$C_n = \frac{1}{n+1}\binom{2n}{n}$. Counts valid parentheses, binary search trees, and polygon triangulations.

Geometric Series Sum

The sum of $a + ar + ar^2...$ is $\frac{a(1-r^n)}{1-r}$. If $|r| < 1$, the infinite sum is $\frac{a}{1-r}$.

Expected Value E[X]

The average outcome of a random variable: $\sum (value \times probability)$. Linearity of Expectation: E[X+Y] = E[X] + E[Y].

Kadane's Algorithm

Finds the maximum sum contiguous subarray in O(n) time using one pass.

Union-Find (DSU)

Data structure for tracking disjoint sets. Optimized by 'Path Compression' and 'Union by Rank' to nearly O(1) per operation.

Fast Fourier Transform (FFT)

Reduces polynomial multiplication from $O(n^2)$ to $O(n \log n)$. Essential for signal processing and large integer math.

Difference Array

Allows O(1) range updates. To add x to [L, R]: diff[L] += x, diff[R+1] -= x. Recover original values via prefix sum.

Z-Algorithm

Finds all occurrences of a pattern P in string T in O(n+m) time by computing longest common prefixes with the start of the string.

Rolling Hash (Rabin-Karp)

Uses a polynomial hash to compare strings in O(1) after O(n) preprocessing. Great for pattern matching.