Why Math in Coding Interviews?
Math problems appear in interviews at all levels — they test logical reasoning and knowledge of mathematical properties that enable elegant O(1) or O(log n) solutions. Common topics: GCD/LCM, prime numbers, modular arithmetic, combinations/permutations, and geometric problems. Having these patterns internalized saves time and demonstrates mathematical maturity.
GCD and LCM
The Euclidean algorithm computes GCD (Greatest Common Divisor) in O(log(min(a,b))) time. gcd(a, b) = gcd(b, a % b), base case gcd(a, 0) = a.
def gcd(a, b):
while b:
a, b = b, a % b
return a
def lcm(a, b):
return a * b // gcd(a, b)
LCM (Least Common Multiple) = a × b / gcd(a, b). Compute GCD first to avoid overflow. Applications: simplify fractions, find the smallest interval that fits both periods, water pouring puzzles.
Prime Numbers
Sieve of Eratosthenes: find all primes up to n in O(n log log n) time. Initialize a boolean array is_prime[0..n] = True. Set is_prime[0] = is_prime[1] = False. For each p from 2 to √n: if is_prime[p], mark all multiples p², p²+p, … as composite.
def sieve(n):
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for p in range(2, int(n**0.5) + 1):
if is_prime[p]:
for multiple in range(p*p, n+1, p):
is_prime[multiple] = False
return [i for i in range(2, n+1) if is_prime[i]]
Primality test for a single number: trial division up to √n. O(√n). For very large numbers (cryptography): Miller-Rabin probabilistic test (O(k log² n) where k = iterations).
Prime factorization: trial division by all primes up to √n. O(√n). Store factorization as a dict {prime: exponent}. Applications: counting divisors (product of (exponent+1) for each prime factor), computing GCD/LCM from factorizations.
Modular Arithmetic
Modular arithmetic is used whenever a problem requires the answer “mod 10^9 + 7” (to prevent integer overflow). 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 mod m: use modular inverse. a / b ≡ a × b^(m-2) (mod m) when m is prime (Fermat’s little theorem). Compute b^(m-2) mod m using fast exponentiation.
Fast modular exponentiation: compute base^exp % mod in O(log exp). Repeated squaring: if exp is even, base^exp = (base^(exp/2))². If odd, base^exp = base × base^(exp-1). Python: pow(base, exp, mod) is built-in and uses fast exponentiation.
Combinations and Pascal’s Triangle
C(n, k) = n! / (k! × (n-k)!) — the number of ways to choose k items from n. Pascal’s rule: C(n, k) = C(n-1, k-1) + C(n-1, k). Build iteratively (Pascal’s triangle) to avoid computing large factorials. For computing C(n, k) mod p: if p is prime and n < p, use modular inverse of k! and (n-k)!. For very large n, use Lucas's theorem.
Applications: counting paths in a grid (C(m+n-2, m-1)), probability calculations, number of subsets of size k.
Classic Interview Problems
Count trailing zeros in n!: count factors of 5 in n! (factors of 2 are more abundant). Count = floor(n/5) + floor(n/25) + floor(n/125) + … O(log n).
Power of N check: for power of 2: n & (n-1) == 0. For power of 3: 3^19 = 1162261467 (largest power of 3 fitting in int); check if (3^19 % n == 0). Similarly for power of 4: is power of 2 and the set bit is in an even position (n & 0xAAAAAAAA == 0).
Number of digit 1s from 1 to n: for each digit position, count how many times that position contributes a 1. O(log n).
Excel column title / column number (LC 168/171): base-26 encoding, but 1-indexed (A=1, Z=26, AA=27). Convert between string and number using modular arithmetic, adjusting for 1-indexed base.
Happy Number (LC 202): repeatedly sum squares of digits. Happy if eventually reaches 1; unhappy if cycles. Floyd’s cycle detection OR detect the cycle by checking if sum has been seen before (set). Key insight: all unhappy numbers eventually reach 4 (known cycle 4→16→37→58→89→145→42→20→4).
Permutation of n! and finding the kth permutation: without generating all permutations, find the kth permutation (1-indexed) directly using factorial number system. O(n²) with a sorted list.
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “How does the Euclidean algorithm compute GCD efficiently?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “The Euclidean algorithm uses the identity gcd(a, b) = gcd(b, a % b) and terminates when b == 0. Each step reduces the problem size by at least half, giving O(log(min(a,b))) time—far faster than trial division. In Python: def gcd(a, b): return a if b == 0 else gcd(b, a % b).” }
},
{
“@type”: “Question”,
“name”: “What is the Sieve of Eratosthenes and when do you use it in interviews?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “The Sieve of Eratosthenes finds all primes up to N in O(N log log N) time and O(N) space by iteratively marking multiples of each prime as composite. Use it when a problem requires many primality checks (e.g., count primes, prime factorization for multiple numbers) and N fits in memory (typically N ≤ 10^6-10^7).” }
},
{
“@type”: “Question”,
“name”: “How does modular arithmetic help avoid integer overflow in competitive programming?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Large intermediate values (e.g., combinations, Fibonacci) overflow 64-bit integers. By applying mod p (usually 10^9+7) after each addition and multiplication—using (a * b) % p and ((a % p) * (b % p)) % p—you keep values bounded. Python's built-in pow(base, exp, mod) computes fast modular exponentiation in O(log exp) time.” }
}
]
}