# Coding Interview: Number Theory and Math Patterns — GCD, Prime Sieve, Modular Arithmetic, Combinatorics

Source: https://www.techinterview.org/post/3233474313/coding-interview-number-theory-math-patterns-gcd-prime-sieve-modular-arithmetic-combinatorics-probability-interview-problems/
Updated: 2026-04-20 · techinterview.org

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.