Math & Number Theory
Mathematical problem-solving patterns used in coding interviews — from modular arithmetic to prime sieves and combinatorics.
Core Concepts
Math problems in interviews test your ability to reason about numbers efficiently. Common patterns include:
- Modular Arithmetic: Use
(a + b) % mto prevent integer overflow. - GCD / LCM: Euclidean algorithm runs in O(log n).
lcm(a,b) = a*b/gcd(a,b). - Sieve of Eratosthenes: Find all primes up to N in O(N log log N).
- Fast Power: Compute x^n in O(log n) via repeated squaring.
- Number of Digits:
floor(log10(n)) + 1.
Cheatsheet Formulas
- GCD (Euclidean):
gcd(a, b) = gcd(b, a % b), base:gcd(n, 0) = n - Fast Power:
x^n = (x^(n/2))^2if n even;x * x^(n-1)if odd - Sum 1..n:
n*(n+1)/2| Sum of squares:n*(n+1)*(2n+1)/6 - Trailing zeros in n!:
floor(n/5) + floor(n/25) + floor(n/125) + ... - Catalan Number:
C(n) = C(2n,n) / (n+1)— counts BSTs, valid parens, etc.