20 articles
Master mathematical algorithms for FAANG DSA interviews: primes, GCD, modular arithmetic, fast exponentiation, combinatorics, and number theory with complexity reference and full problem index.
LC 204 Count Primes is the gateway sieve problem at Google and Amazon. Master the Sieve of Eratosthenes, understand why you start marking at p*p, and apply the technique to interval queries, prime factorization, and every sieve variant an interviewer can ask.
LC 1979 Find Greatest Common Divisor of Array is the entry point to GCD problems at Google and Meta. Master the Euclidean algorithm in O(log n), compute LCM without overflow, and apply extended GCD for modular inverse.
Modular arithmetic powers nearly every competitive programming problem and is foundational at Google, Stripe, and any system that handles big numbers. Master binary exponentiation in O(log n), modular inverse via Fermat little theorem, and the modulo identities that prevent overflow on the hot path.
Prime factorization is the workhorse of number-theoretic interview problems at Amazon and Microsoft. Master trial division in O(sqrt n), the smallest-prime-factor sieve for batched factorization in O(log n) per query, and the divisor-counting tricks they unlock.
Eulers totient function phi(n) counts integers up to n coprime to n and underpins RSA, modular inverse for composite moduli, and Eulers theorem. Master the prime-factorization formula, the sieve variant in O(N log log N), and the multiplicative-function tricks that make phi indispensable for competitive programming.
Computing C(n, r) modulo a prime appears in nearly every counting problem at Google and Meta. Master Pascal triangle for small n, precomputed factorials with modular inverse for n up to 10^6, and Lucas theorem for n up to 10^18.
Number theory basics — divisibility, congruences, digit DP, perfect numbers — power half of the math problems at Amazon and Microsoft. Master the divisibility rules, modular congruence properties, and digit-extraction tricks before tackling advanced number theory.
Matrix exponentiation collapses any linear recurrence into O(log n) by raising a transition matrix to the n-th power. Master Fibonacci, k-th order recurrences, and DP optimization tricks that let you answer queries with n up to 10^18 in milliseconds.
Bit manipulation is the cheat code of competitive programming and tier-1 interviews. Master the XOR identities, n & (n-1) tricks, subset enumeration over a bitmask, and bitmask DP techniques that turn O(2^n) brute force into elegant constant-factor wins.
Recognising classical number sequences — Fibonacci, Catalan, triangular, Pascal-derived — is the difference between a 30-minute brute force and a 5-minute closed form. Master the recurrences, generating functions, and combinatorial interpretations every interviewer expects you to know.
Learn the Chinese Remainder Theorem from scratch. Understand the math, build CRT from extended GCD, handle non-coprime moduli, and ace cryptography and competitive programming interview questions.
Master square root decomposition for range sum, range minimum, and Mo's algorithm. The simplest range-query data structure that beats brute force for competitive programming and interviews.
Avoid silent overflow bugs and floating-point traps. Learn safe multiplication, modular arithmetic, BigInt, integer square root, and binary search on the answer for competitive programming and interviews.
Solve probability DP problems used by quantitative interviews. Master expected value recurrences, geometric distribution, knight probability, and the soup servings memoization trick.
Master the computational geometry primitives every interviewer expects: cross product orientation, segment intersection, Graham scan convex hull, polygon area via shoelace, and point in polygon.
Master combinatorial game theory: Nim XOR strategy, Grundy numbers, Sprague-Grundy theorem, mex, and minimax DP for stone games and impartial games in competitive programming and interviews.
Master randomized algorithms in interviews: reservoir sampling for streams, quickselect for O(n) kth element, Fisher-Yates shuffle, and Bloom filters with probability proofs.
Apply the inclusion-exclusion principle to divisibility counting, derangements, Euler totient, and surjection problems. The single most useful tool for combinatorial counting in interviews and competitive programming.
Complete reference for math and number theory DSA patterns: algorithm selection guide, complexity table, template library, and top 25 interview problems ranked by FAANG frequency.