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.
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “Why does the Sieve of Eratosthenes start marking from i*i instead of 2*i?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “When processing prime p, all composites smaller than p*p have already been marked by smaller primes. For example, when processing p=7: 2*7=14 was already marked by 2; 3*7=21 was already marked by 3; 5*7=35 was already marked by 5. The first unmarked multiple of p is p*p=49. Starting from p*p avoids redundant work and makes the inner loop run fewer iterations total. This is the optimization that gives the sieve its O(N log log N) complexity instead of O(N log N) if starting from 2*p. The outer loop runs only up to sqrt(N) because any composite N must have a factor <= sqrt(N) — if all numbers up to sqrt(N) are checked, all composites up to N are already marked."
}
},
{
"@type": "Question",
"name": "How does fast exponentiation (exponentiation by squaring) work?",
"acceptedAnswer": {
"@type": "Answer",
"text": "Key insight: base^exp can be computed using the binary representation of exp. If the current bit of exp is 1: multiply the result by the current base power. Always square the base for the next bit. Example: 3^13 (13 in binary = 1101). bit 0 (1): result *= 3^1 = 3. bit 1 (0): skip. bit 2 (1): result *= 3^4 = 3*81 = 243. bit 3 (1): result *= 3^8 = 243*6561 = 1594323. Total: 4 multiplications instead of 12 for naive multiplication. With modular arithmetic: apply % mod after each multiplication to keep numbers small. O(log exp) multiplications. Python's built-in pow(base, exp, mod) uses this algorithm and is highly optimized in C."
}
},
{
"@type": "Question",
"name": "How do you compute modular inverse for division in modular arithmetic?",
"acceptedAnswer": {
"@type": "Answer",
"text": "Division (a / b) mod M requires computing the modular inverse of b: a value b_inv such that b * b_inv u2261 1 (mod M). Method 1 — Fermat's Little Theorem: if M is prime and b is not divisible by M, then b_inv = pow(b, M-2, M). This uses fast exponentiation: O(log M). Method 2 — Extended Euclidean Algorithm: works for any M (not just prime). Returns x, y such that b*x + M*y = gcd(b, M). If gcd(b,M)=1, then x is the inverse. O(log M). When to use: Fermat is simpler (one line in Python) but requires M to be prime. Extended GCD works for composite M. In competitive programming, M is almost always a prime like 10^9+7."
}
},
{
"@type": "Question",
"name": "What is digit DP and when should you use it?",
"acceptedAnswer": {
"@type": "Answer",
"text": "Digit DP counts integers in a range [0, N] satisfying a condition on their decimal (or binary) digits. The key is constructing the number digit by digit, left to right, while tracking: (1) position in the number, (2) tight — whether the prefix is still equal to N's prefix (constrains the maximum digit we can place), (3) problem-specific state (digit sum, last digit, count of some digit). At each position, try digits 0-9 (or 0 to N[pos] if tight). Memoize on (position, tight, state). Return the total valid count. This avoids iterating over all N integers — instead the DP table has O(digits * 2 * state_size) entries. Use when you can't derive a closed-form formula and the state per digit fits in a manageable table. LC 233 (count 1s in 1..N), LC 902 (numbers at most N using given digits), LC 1067 (digit count)."
}
},
{
"@type": "Question",
"name": "How do you handle combinations with large n and modular arithmetic?",
"acceptedAnswer": {
"@type": "Answer",
"text": "C(n, k) = n! / (k! * (n-k)!) mod M. Direct computation fails for large n because factorials overflow. Solution: precompute factorials and inverse factorials up to max_n. factorial[i] = i! % M. inv_factorial[i] = pow(factorial[i], M-2, M) (Fermat). Then C(n, k) = factorial[n] * inv_factorial[k] % M * inv_factorial[n-k] % M. Precomputation: O(max_n) time and space. Each query: O(1). This pattern appears in counting paths, combinations, and any problem asking for "count of ways" modulo a prime. Alternative: Lucas' theorem for C(n, k) mod p when p is prime and n, k can be huge (larger than max_n): express n and k in base p and apply C(n_i, k_i) mod p for each digit."
}
}
]
}
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: Coinbase Interview Guide
Asked at: LinkedIn Interview Guide