Math-based problems appear in approximately 10% of coding interviews and are often considered the hardest category because the solutions require mathematical insight rather than algorithmic templates. This guide covers the essential number theory and math patterns: GCD, prime testing, modular arithmetic, and combinatorics — giving you the tools to handle these problems systematically.
GCD and LCM
Greatest Common Divisor (GCD): the largest number that divides both a and b. Euclidean algorithm: gcd(a, b) = gcd(b, a % b). Base case: gcd(a, 0) = a. Time: O(log(min(a, b))). Example: gcd(48, 18) = gcd(18, 12) = gcd(12, 6) = gcd(6, 0) = 6. Least Common Multiple: lcm(a, b) = a * b / gcd(a, b). Use this formula to avoid overflow: lcm = a / gcd(a, b) * b (divide first). Applications: (1) Fraction simplification — reduce a/b by dividing both by gcd(a, b). (2) GCD of an array — iteratively compute gcd of all elements. gcd(a, b, c) = gcd(gcd(a, b), c). (3) Check if two rectangles tile perfectly — the square side length that tiles both dimensions is gcd(width, height). Interview problems: GCD of Strings (“ABCABC” and “ABC” have GCD string “ABC” — check if both strings are composed of the same repeating unit), Water Pouring (GCD determines reachable volumes), and Fraction Addition (find common denominator using LCM).
Prime Numbers and Sieve
Primality test: for a number N, check if any integer from 2 to sqrt(N) divides it. If none do, N is prime. Time: O(sqrt(N)). Optimization: check 2, then only odd numbers. Or check 2, 3, then numbers of form 6k+/-1 (all primes > 3 are of this form). Sieve of Eratosthenes: find all primes up to N. Create a boolean array is_prime[0..N], initialize all to true. Set is_prime[0] = is_prime[1] = false. For each i from 2 to sqrt(N): if is_prime[i], mark all multiples of i as composite (starting from i*i). Time: O(N log log N). Space: O(N). All remaining true entries are primes. Count Primes (LeetCode 204): direct application of the Sieve. Prime factorization: divide N by each prime starting from 2. For each prime p that divides N, count how many times and divide N by p. Continue until N = 1. The factors are the primes used. Time: O(sqrt(N)). Applications: GCD/LCM computations, finding the number of divisors (from prime factorization, count = product of (exponent + 1) for each prime factor), and Ugly Numbers (numbers whose only prime factors are 2, 3, and 5).
Modular Arithmetic
Many problems require computing results modulo 10^9 + 7 (a large prime, chosen to prevent overflow while fitting in 32-bit integers after multiplication of two 32-bit numbers). Key properties: (a + b) % m = ((a % m) + (b % m)) % m. (a * b) % m = ((a % m) * (b % m)) % m. (a – b) % m = ((a % m) – (b % m) + m) % m (add m to handle negative results). Division: (a / b) % m = (a * b^(-1)) % m where b^(-1) is the modular inverse. For prime m: b^(-1) = b^(m-2) % m (Fermat little theorem). Compute with fast exponentiation. Fast exponentiation (power mod): compute a^n % m in O(log n). If n is even: a^n = (a^(n/2))^2. If n is odd: a^n = a * a^(n-1). Recursive or iterative with bit manipulation. Interview problems: any DP or combinatorics problem with “return the answer modulo 10^9 + 7.” Count paths, count subsequences, count arrangements — all use modular arithmetic to prevent overflow. The key mistake: forgetting to take modulo at each step (overflow corrupts intermediate results even if you take modulo at the end).
Combinatorics
Combinations: C(n, k) = n! / (k! * (n-k)!). Compute iteratively to avoid overflow: C(n, k) = C(n, k-1) * (n – k + 1) / k. Or use Pascal triangle: C(n, k) = C(n-1, k-1) + C(n-1, k). For modular combinatorics: precompute factorials and inverse factorials modulo 10^9+7. C(n, k) = fact[n] * inv_fact[k] * inv_fact[n-k] % MOD. Permutations: P(n, k) = n! / (n-k)!. The number of ways to arrange k items from n. Catalan numbers: C_n = C(2n, n) / (n+1). Counts: number of valid parentheses sequences of length 2n, number of BSTs with n nodes, number of paths in a grid that do not cross the diagonal. Inclusion-exclusion: to count elements in A union B union C: |A| + |B| + |C| – |A intersect B| – |A intersect C| – |B intersect C| + |A intersect B intersect C|. Used for: count numbers not divisible by any prime in a set, count derangements. Interview problems: Unique Paths (C(m+n-2, m-1)), Catalan Number applications, and any “count the number of ways” problem with modular arithmetic.
Common Math Interview Problems
Problems to practice: (1) Pow(x, n) — fast exponentiation. Handle negative n: x^(-n) = 1/x^n. O(log n). (2) Count Primes — Sieve of Eratosthenes. (3) GCD of Strings — check if both strings are composed of the same unit. GCD of lengths determines the unit length. (4) Ugly Number II — find the nth number whose prime factors are only 2, 3, 5. Use three pointers or a min-heap. (5) Happy Number — repeatedly sum the squares of digits until reaching 1 (happy) or a cycle (not happy). Use fast-slow pointer cycle detection. (6) Integer to Roman / Roman to Integer — mapping table + greedy. (7) Excel Sheet Column Number — base-26 conversion. (8) Factorial Trailing Zeroes — count factors of 5 in n!: n/5 + n/25 + n/125 + … (9) Unique Paths — C(m+n-2, m-1) or DP. (10) Random Pick with Weight — prefix sum + binary search. Pattern recognition: if the problem involves divisibility, think GCD. If it involves counting arrangements, think combinatorics. If it involves “modulo 10^9+7,” precompute factorials. If it involves large exponents, use fast exponentiation.