Math and Number Theory for DSA — Complete Interview Guide

Why Math and Number Theory in DSA?#

Mathematical algorithms power cryptography, combinatorics, and competitive programming. Understanding number theory unlocks O(log n) solutions to problems that naive approaches solve in O(n) or worse. Google, Meta, and Amazon ask math problems in 20-30% of coding rounds — they signal the ability to reduce brute force to elegant formulas.

Core Topics#

1. Prime Numbers#

• Sieve of Eratosthenes — generate all primes up to n in O(n log log n)
• Segmented Sieve — large ranges with O(sqrt(n)) memory
• Miller-Rabin — probabilistic primality test in O(k log^2 n)
• Smallest Prime Factor (SPF) sieve — factorize any number up to n in O(log n)

2. GCD and LCM#

• Euclidean algorithm — GCD(a, b) = GCD(b, a mod b) in O(log min(a,b))
• Extended Euclidean — computes Bezout coefficients alongside GCD
• LCM formula — LCM(a, b) = a / GCD(a, b) * b (divide first to avoid overflow)

3. Modular Arithmetic#

• Addition: (a + b) % m
• Multiplication: (a * b) % m
• Modular inverse — pow(a, m-2, m) via Fermat's little theorem (m must be prime)
• Extended GCD inverse — works for any coprime a, m
• Chinese Remainder Theorem — solve simultaneous modular equations

4. Fast Exponentiation#

• Binary exponentiation — a^n mod m in O(log n) via repeated squaring
• Matrix exponentiation — compute Fibonacci or linear recurrences in O(log n)

5. Combinatorics#

• nCr with precomputed factorials — O(n) build, O(1) query
• Pascal's triangle — O(n^2) build, useful for small n
• Catalan numbers — C(n) = nC(2n) / (n+1); counts BSTs, balanced parentheses, triangulations

6. Number Theory#

• Euler's totient function — count integers coprime to n in [1, n]
• Prime factorization — O(sqrt(n)) trial division
• Divisor count/sum — from prime factorization, multiply (e_i + 1) for count

Complexity Summary#

Template Library#

MOD = 10**9 + 7
 
# Fast power: a^e mod m in O(log e)
def pw(b, e, m=MOD):
    return pow(b, e, m)
 
# Modular inverse (prime modulus only — uses Fermat's little theorem)
def inv(a, m=MOD):
    return pow(a, m - 2, m)
 
# GCD and LCM
from math import gcd
def lcm(a, b):
    return a // gcd(a, b) * b   # divide FIRST to avoid overflow
 
# Precomputed factorials for nCr mod prime
def build_fact(n, m=MOD):
    f = [1] * (n + 1)
    for i in range(1, n + 1):
        f[i] = f[i-1] * i % m
    fi = [1] * (n + 1)
    fi[n] = inv(f[n])
    for i in range(n - 1, -1, -1):
        fi[i] = fi[i+1] * (i+1) % m
    return lambda n, k: f[n] * fi[k] % m * fi[n-k] % m if 0 <= k <= n else 0
 
C = build_fact(10**6)
 
# Sieve of Eratosthenes
def sieve(n):
    p = [True] * (n + 1)
    p[0] = p[1] = False
    for i in range(2, int(n**0.5) + 1):
        if p[i]:
            for j in range(i*i, n+1, i):
                p[j] = False
    return p
 
# Smallest Prime Factor sieve (for O(log n) factorization)
def spf_sieve(n):
    s = list(range(n + 1))
    for i in range(2, int(n**0.5) + 1):
        if s[i] == i:   # i is prime
            for j in range(i*i, n+1, i):
                if s[j] == j:
                    s[j] = i
    return s

Algorithm Selection Guide#

Common Pitfalls#

1. LCM overflow. Always compute a / gcd(a, b) * b, not a * b / gcd(a, b). For a = b = 10^9, the product overflows 32-bit integers.
2. Fermat inverse only valid for prime modulus. If the modulus is not prime, use Extended Euclidean.
3. Float comparison. Use abs(a - b) < 1e-9, never a == b for floating-point values.
4. GCD of 0. gcd(0, n) = n by definition. Handle in LCM to avoid division by zero.
5. Sieve inner loop at p^2, not 2p. Starting at 2p is correct but halves performance on large inputs.
6. nCr inline for large n. Always precompute factorials; computing nCr inline overflows and is slow.

Key Takeaways#

• The Sieve of Eratosthenes is the standard tool whenever you need primality for many numbers up to n in O(n log log n).
• The Euclidean GCD algorithm runs in O(log n) — it is both ancient and optimal, and underlies LCM, modular inverse, and CRT.
• Always divide before multiplying in LCM to prevent overflow: a // gcd(a, b) * b.
• Fermat's little theorem gives modular inverse in O(log n) but only when the modulus is prime; use Extended GCD otherwise.
• Binary exponentiation computes a^n mod m in O(log n) by squaring at each bit of the exponent.
• The SPF sieve lets you factorize any number up to n in O(log n) after O(n log log n) preprocessing — essential for factorization-heavy problems.
• Math problems often have O(1) closed-form solutions — always look for the formula before reaching for a loop.