When Math Problems Appear
Math interview problems test number theory, combinatorics, and modular arithmetic. Common patterns: prime checking and sieve, fast exponentiation (power with modulus), GCD/LCM, factorials and combinations, and digit manipulation. These appear in problems involving large numbers (use modular arithmetic), counting problems (combinations, permutations), and optimization with number-theoretic constraints.
Sieve of Eratosthenes
Find all primes up to N in O(N log log N) time. Create a boolean array is_prime[0..N]. Mark is_prime[0] = is_prime[1] = False. For each i from 2 to sqrt(N): if is_prime[i]: mark all multiples of i starting from i^2 as composite. After the loop, is_prime[i] is True iff i is prime.
def sieve(n):
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(n**0.5) + 1):
if is_prime[i]:
for j in range(i*i, n+1, i):
is_prime[j] = False
return [i for i in range(n+1) if is_prime[i]]LC 204 (Count Primes), LC 762 (Prime Number of Set Bits). For single prime check: trial division up to sqrt(n) in O(sqrt(n)).
Fast Power (Exponentiation by Squaring)
Compute base^exp % mod in O(log exp) instead of O(exp). Key: base^8 = (base^4)^2 = ((base^2)^2)^2 — only 3 multiplications instead of 7.
def fast_pow(base, exp, mod):
result = 1
base %= mod
while exp > 0:
if exp % 2 == 1: # current bit is set
result = result * base % mod
base = base * base % mod
exp //= 2
return resultUsed in: LC 50 (Pow(x,n)), LC 372 (Super Pow), cryptography (RSA modular exponentiation), and problems requiring (a^b) % MOD where b is huge. Python has built-in: pow(base, exp, mod) is already O(log exp).
GCD and LCM
Euclidean algorithm: gcd(a, b) = gcd(b, a % b). Base case: gcd(a, 0) = a. O(log min(a, b)). LCM: lcm(a, b) = a * b // gcd(a, b). Apply modular arithmetic carefully: (a * b) may overflow before the division. Use: a // gcd(a,b) * b instead. Applications: LC 1071 (Greatest Common Divisor of Strings), LC 858 (Mirror Reflection), LC 365 (Water and Jug Problem — solvable iff target is a multiple of gcd(jug1, jug2)).
Combinations and Pascal’s Triangle
C(n, k) = n! / (k! * (n-k)!). For large n with modular arithmetic: use Fermat’s little theorem. If MOD is prime: C(n,k) % MOD = n! * mod_inverse(k!) * mod_inverse((n-k)!) % MOD. mod_inverse(x) = pow(x, MOD-2, MOD) (Fermat’s little theorem). Precompute factorials and inverse factorials up to N for O(1) combination queries. Pascal’s triangle for small n: dp[i][j] = dp[i-1][j-1] + dp[i-1][j]. Use when n <= 1000. LC 62 (Unique Paths): C(m+n-2, m-1). LC 1641 (Count Sorted Vowel Strings): combinatorics stars-and-bars.
Digit DP Pattern
Count numbers in [1, N] satisfying a property on their digits (e.g., no two adjacent digits are the same, sum of digits is divisible by K). State: (position, tight, carry_or_sum, …). Tight: whether the current prefix is still bounded by N’s digits (allows digits 0 to N[pos] if tight, else 0 to 9). Build the count by choosing each digit and recursing. Memoize on (position, tight, other_state). O(digits * 10 * state_size). LC 233 (Number of Digit One), LC 357 (Count Numbers with Unique Digits), LC 902 (Numbers At Most N Given Digit Set).
Modular Arithmetic Rules
(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 prevent negative). Division: (a / b) % M = (a * mod_inverse(b)) % M — only valid when M is prime (Fermat) or when gcd(b, M) = 1 (extended Euclidean). Apply modular reduction at each step to prevent integer overflow in languages without arbitrary precision. In Python, integers are arbitrary precision, but in Java/C++, apply % after each multiplication.
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: Coinbase Interview Guide
Asked at: LinkedIn Interview Guide