DSA: Mathematical Algorithms

Master primes, GCD, modular arithmetic, combinatorics, and number theory essentials.

Sieve of Eratosthenes

Find all prime numbers up to n in O(n log log n). Mark multiples of each prime starting from p² as composite.

Sieve of Eratosthenes

Boolean array isPrime[0..n]. Mark composites by iterating multiples of each prime found.

  • Start from p = 2; mark p², p²+p, p²+2p, ... as composite
  • Start from p² because smaller multiples were already marked by earlier primes
  • Only iterate p up to sqrt(n): all composites above sqrt(n) have a factor below it
  • Time: O(n log log n), Space: O(n)

Sieve of Eratosthenes

C++

Mark multiples of each prime starting from p²; collect unmarked indices.

GCD and LCM (Euclidean Algorithm)

The Euclidean algorithm computes GCD(a, b) = GCD(b, a % b) recursively until b = 0. LCM follows from the identity: LCM(a, b) = a * b / GCD(a, b).

GCD and LCM

GCD(a, b) = GCD(b, a % b). Base case: GCD(a, 0) = a. Time: O(log(min(a, b))).

  • Euclidean algorithm: each step reduces the problem size by at least half
  • LCM(a, b) = (a / GCD(a, b)) * b, divide first to avoid overflow
  • GCD of array: fold pairwise GCD left to right
  • Extended Euclidean finds x, y such that ax + by = GCD(a, b)

GCD and LCM

C++

Euclidean GCD in O(log min(a,b)); LCM via GCD identity.

Fast Exponentiation and Modular Exponentiation

Compute x^n in O(log n) by squaring: x^n = (x^(n/2))² for even n, and x * x^(n-1) for odd n. Modular version applies mod at each step to prevent overflow.

Fast / Modular Exponentiation

Halve the exponent each step: O(log n) multiplications instead of O(n).

  • Even n: power(x, n) = power(x, n/2)²
  • Odd n: power(x, n) = x * power(x, n-1)
  • Modular: apply % mod after every multiplication to keep numbers small
  • Essential for competitive programming where answers are mod 10^9+7

Modular Exponentiation

C++

Iterative fast power with mod at each step: O(log exp), no overflow.

Prime Factorization and Divisors

Find all prime factors of n in O(sqrt(n)) by trial division up to sqrt(n). Count all divisors using the fact that divisors come in pairs (d, n/d) around sqrt(n).

Prime Factorization

Divide by each integer from 2 to sqrt(n). Any remaining value greater than 1 is a prime factor.

  • Divide out all 2s first, then check odd numbers from 3 to sqrt(n)
  • If n > 1 after the loop, n itself is prime
  • Count divisors: for i = 1 to sqrt(n), count pairs (i, n/i); handle perfect squares
  • Sum of divisors, product of divisors: same O(sqrt(n)) loop

Prime Factorization and Count Divisors

C++

Trial division to sqrt(n); divisors come in pairs around sqrt(n).

nCr and Pascal's Triangle

Pascal's triangle builds nCr values using the recurrence C(n, k) = C(n-1, k-1) + C(n-1, k). For large n with modular arithmetic, use modular inverse of factorials.

nCr Computation

Pascal's triangle: O(n²) DP. Factorial method with modular inverse: O(n) precompute, O(1) query.

  • Pascal recurrence: C(n, k) = C(n-1, k-1) + C(n-1, k)
  • Base cases: C(n, 0) = C(n, n) = 1
  • Modular nCr: precompute fact[], inv_fact[] using modPow(fact[n], MOD-2, MOD)
  • Fermat's little theorem: a^(MOD-2) ≡ a^(-1) (mod MOD) when MOD is prime

Pascal's Triangle / nCr

C++

2D DP: C(n,k) = C(n-1,k-1) + C(n-1,k) from row 0 up.

Catalan Numbers

The nth Catalan number counts many combinatorial structures: balanced parentheses, BST shapes, triangulations of polygons, and more. Formula: C(2n, n) / (n + 1).

Catalan Numbers

Catalan(n) = C(2n, n) / (n+1). DP recurrence: Cat(n) = sum of Cat(i) * Cat(n-1-i) for i = 0..n-1.

  • Cat(0) = 1, Cat(1) = 1, Cat(2) = 2, Cat(3) = 5, Cat(4) = 14
  • Counts: valid bracket sequences of length 2n
  • Counts: BSTs with n distinct keys
  • Counts: ways to triangulate a convex polygon with n+2 sides
  • Grows as 4^n / (n^(3/2) * sqrt(pi))

Catalan Numbers

C++

DP recurrence: Cat(n) = sum of Cat(i)*Cat(n-1-i). Counts bracket sequences and BST shapes.

Modular Arithmetic and Trailing Zeros

Two essential number theory tools: modular arithmetic rules for addition/multiplication, and counting trailing zeros in n! by counting factors of 5.

Modular Arithmetic

(a + b) % m = ((a % m) + (b % m)) % m. Same holds for multiplication. NOT for division (use modular inverse).

  • Trailing zeros in n! = floor(n/5) + floor(n/25) + floor(n/125) + ...
  • Each factor of 10 needs one 2 and one 5; factors of 2 always exceed factors of 5
  • Modular inverse of a mod prime p: a^(p-2) mod p (Fermat's little theorem)
  • Use long long for intermediate products before applying mod

Trailing Zeros in n! and Modular Inverse

C++

Count factors of 5 for zeros; Fermat's theorem for modular inverse.

Mathematical Algorithms Reference

Quick reference for all algorithms covered on this page.

AlgorithmTimeKey Formula / Recurrence
Sieve of EratosthenesO(n log log n)Mark multiples of p from p² upward
Euclidean GCDO(log min(a,b))GCD(a, b) = GCD(b, a % b)
LCMO(log min(a,b))LCM(a,b) = a / GCD(a,b) * b
Fast ExponentiationO(log n)x^n = (x^(n/2))² or x*(x^(n-1))
Modular ExponentiationO(log exp)Apply % mod after each multiply
Prime FactorizationO(sqrt(n))Trial division up to sqrt(n)
Pascal's Triangle / nCrO(n²) build, O(1) queryC(n,k) = C(n-1,k-1) + C(n-1,k)
Catalan NumbersO(n²)Cat(n) = sum Cat(i)*Cat(n-1-i)
Trailing Zeros in n!O(log n)sum of floor(n/5^k)
Modular InverseO(log mod)Fermat: a^(mod-2) mod mod

Knowledge Check

1. Sieve of Eratosthenes finds all primes up to n in:

2. Euclidean algorithm: GCD(a, b) = ?

3. Fast exponentiation (x^n) runs in:

4. Modular exponentiation computes (base^exp) % mod. Why use modular arithmetic?

5. The nth Catalan number formula is:

6. Number of trailing zeros in n! equals:

7. Pascal's triangle entry C(n, k) equals:

8. Prime factorization of n by trial division runs in:

PreviousNext