Math for Coding Interviews: GCD, Modular Arithmetic, Primes and Combinatorics

Math problems are the ones candidates skip in preparation and then lose easy points on in online assessments. The good news: the set of number theory that interviews actually use is small and stable. This guide covers that set from first principles, with C++ and Python implementations verified against the LeetCode examples, and shows which interview problems each tool unlocks.

What Math Is Actually Asked in Coding Interviews

If you are aiming at Codeforces or CodeChef ratings as well, the heavier topics are covered in the competitive programming roadmap. For SDE interviews, master the first five rows.

Modular Arithmetic and Why 10^9 + 7

When a problem says "return the answer modulo 10⁹ + 7", the real answer would overflow 64 bits. You keep every intermediate value reduced. The rules:

Why this specific number? 10⁹ + 7 is prime, so every non-zero residue has an inverse (needed for nCr and division). It is just under 2³⁰, so sums fit in a signed 32-bit int and products fit in a signed 64-bit int. 998244353 is the other common modulus; it is prime too and has a special structure used by number-theoretic transforms.

GCD, LCM and the Extended Euclidean Algorithm

Euclid's algorithm: gcd(a, b) = gcd(b, a mod b), and gcd(a, 0) = a. It works because any common divisor of a and b also divides a - k·b, which includes a mod b. It takes O(log min(a, b)) steps; the worst case is consecutive Fibonacci numbers.

long long gcdLL(long long a, long long b) {
    while (b != 0) {
        long long t = a % b;
        a = b;
        b = t;
    }
    return a;
}
long long lcmLL(long long a, long long b) { return a / gcdLL(a, b) * b; }  // divide first

// returns g = gcd(a, b) and sets x, y with a*x + b*y = g
long long extGcd(long long a, long long b, long long& x, long long& y) {
    if (b == 0) { x = 1; y = 0; return a; }
    long long x1, y1;
    long long g = extGcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def ext_gcd(a, b):
    """Return (g, x, y) with a*x + b*y == g == gcd(a, b)."""
    if b == 0:
        return a, 1, 0
    g, x1, y1 = ext_gcd(b, a % b)
    return g, y1, x1 - (a // b) * y1

Dry run of gcd(48, 18): (48, 18) → (18, 12) → (12, 6) → (6, 0) → 6. And ext_gcd(30, 12) returns (6, 1, -2): 30 × 1 + 12 × (-2) = 6. Built-ins exist in all three languages (std::gcd/std::lcm in C++17, math.gcd/math.lcm in Python 3.9+), but interviewers sometimes ask you to write Euclid yourself.

Where GCD appears:

• Greatest Common Divisor of Strings (LC 1071): if s1 + s2 == s2 + s1, the answer is the prefix of length gcd(len1, len2), otherwise empty.
• Max Points on a Line (LC 149): represent each slope as a reduced fraction (dy/g, dx/g) with a normalised sign, avoiding floating point.
• Water and Jug Problem (LC 365): target t is reachable iff t <= x + y and t is a multiple of gcd(x, y) (Bézout's identity).
• Rotate Array via juggling: the rotation splits into gcd(n, k) cycles.

Primes: Trial Division, the Sieve and Factorisation

Is one number prime?

Check divisors up to √n: if n = a × b with a ≤ b then a ≤ √n. O(√n) per number, fine for a single n up to about 10¹² to 10¹⁴. Write the loop as p * p <= n to avoid floating-point sqrt errors.

All primes up to n: Sieve of Eratosthenes

Mark every number as prime, then for each prime i cross out its multiples starting from i * i (smaller multiples were already crossed out by smaller primes). Total work is n/2 + n/3 + n/5 + ... over primes, which is O(n log log n).

vector<bool> sieve(int n) {
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = false;
    if (n >= 1) isPrime[1] = false;
    for (long long i = 2; i * i <= n; i++)
        if (isPrime[i])
            for (long long j = i * i; j <= n; j += i)
                isPrime[j] = false;
    return isPrime;
}

def count_primes(n):
    """LeetCode 204: number of primes strictly less than n."""
    if n < 3:
        return 0
    is_prime = bytearray([1]) * n
    is_prime[0] = is_prime[1] = 0
    i = 2
    while i * i < n:
        if is_prime[i]:
            is_prime[i * i::i] = bytearray(len(range(i * i, n, i)))
        i += 1
    return sum(is_prime)

The Python version uses slice assignment so the inner loop runs in C; a plain Python inner loop is several times slower and can time out at n = 5 × 10⁶. Our run returns 4 for n = 10 and 348,513 for n = 5 × 10⁶, the known prime count.

Factorising many numbers: smallest prime factor sieve

Store spf[x], the smallest prime dividing x. Then factorise any x ≤ n by repeatedly dividing by spf[x], which takes O(log x) steps because each division at least halves x.

vector<int> smallestPrimeFactor(int n) {
    vector<int> spf(n + 1);
    iota(spf.begin(), spf.end(), 0);
    for (long long i = 2; i * i <= n; i++)
        if (spf[i] == i)                       // i is prime
            for (long long j = i * i; j <= n; j += i)
                if (spf[j] == j) spf[j] = i;
    return spf;
}
// factorise 84: 2, 2, 3, 7
// while (x > 1) { int p = spf[x]; x /= p; }

For a single large number, trial division with exponent counting is enough: 360 = 2^3 · 3^2 · 5. Factorisation gives you the number of divisors (product of (e + 1)), the sum of divisors, and Euler's totient if a problem ever needs it.

Fast Exponentiation (Binary Exponentiation)

To compute b^e, write e in binary. b¹³ = b⁸ · b⁴ · b¹ since 13 = 1101₂. Repeatedly square the base and multiply it into the result when the current bit is set. O(log e) multiplications instead of e.

long long power(long long base, long long exp, long long mod) {
    long long result = 1 % mod;      // handles mod == 1
    base %= mod;
    if (base < 0) base += mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

def power(base, exp, mod):
    result = 1 % mod
    base %= mod
    while exp > 0:
        if exp & 1:
            result = result * base % mod
        base = base * base % mod
        exp >>= 1
    return result
# Python's built-in pow(base, exp, mod) does the same, and is what you should use.

Dry run of 3¹³: bits of 13 from the right are 1, 0, 1, 1. Result picks up 3, skips 9, picks up 81, picks up 6561: 3 × 81 × 6561 = 1,594,323 = 3¹³. Four squarings instead of twelve multiplications.

LeetCode 50: Pow(x, n)

The same loop on doubles, with two traps: negative n (use 1/x and -n), and n = INT_MIN, where -n overflows an int. Copy n into a 64-bit variable first.

double myPow(double x, int n) {
    long long e = n;                 // -INT_MIN overflows int, not long long
    if (e < 0) { x = 1 / x; e = -e; }
    double result = 1;
    while (e > 0) {
        if (e & 1) result *= x;
        x *= x;
        e >>= 1;
    }
    return result;
}

Count Good Numbers (LC 1922) is fast power in disguise: even indices have 5 choices (even digits), odd indices have 4 (prime digits), so the answer is 5^ceil(n/2) · 4^floor(n/2) mod p with n up to 10¹⁵. For n = 4 this gives 25 × 16 = 400. The same squaring idea on 2×2 matrices computes the n-th Fibonacci number in O(log n), a favourite follow-up.

Modular Inverse: Fermat and Extended Euclid

The inverse of a modulo m is the x with a · x ≡ 1 (mod m). It exists iff gcd(a, m) = 1.

• Prime modulus (the usual case): Fermat's little theorem says a^p-1 ≡ 1 (mod p), so a^p-2 is the inverse. One fast power, O(log p). For p = 10⁹+7, the inverse of 3 is 333,333,336 (check: 3 × 333,333,336 = 1,000,000,008 ≡ 1).
• Any modulus: extended Euclid gives x and y with a·x + m·y = 1, so x mod m is the inverse. Inverse of 3 mod 10 is 7; 4 has no inverse mod 10 because gcd(4, 10) = 2.

long long modInverse(long long a, long long p) {        // p prime, a % p != 0
    return power(a, p - 2, p);
}
long long modInverseExt(long long a, long long m) {      // any m
    long long x, y;
    long long g = extGcd(a, m, x, y);
    if (g != 1) return -1;                               // no inverse
    return ((x % m) + m) % m;
}

In Python 3.8+, pow(a, -1, m) computes the modular inverse directly and raises ValueError if none exists.

nCr mod p: Factorials and Inverse Factorials

C(n, r) = n! / (r! (n-r)!). Under a prime modulus, replace the division with inverses. Computing each inverse separately costs O(log p) per query; precomputing inverse factorials makes every query O(1).

const long long MOD = 1'000'000'007LL;

struct Combinatorics {
    vector<long long> fact, invFact;
    Combinatorics(int n) : fact(n + 1), invFact(n + 1) {
        fact[0] = 1;
        for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;
        invFact[n] = power(fact[n], MOD - 2, MOD);       // one inverse
        for (int i = n; i > 0; i--) invFact[i - 1] = invFact[i] * i % MOD;
    }
    long long nCr(int n, int r) const {
        if (r < 0 || r > n) return 0;
        return fact[n] * invFact[r] % MOD * invFact[n - r] % MOD;
    }
};

MOD = 10**9 + 7

class Combinatorics:
    def __init__(self, n, mod=MOD):
        self.mod = mod
        self.fact = [1] * (n + 1)
        for i in range(1, n + 1):
            self.fact[i] = self.fact[i - 1] * i % mod
        self.inv_fact = [1] * (n + 1)
        self.inv_fact[n] = pow(self.fact[n], mod - 2, mod)
        for i in range(n, 0, -1):
            self.inv_fact[i - 1] = self.inv_fact[i] * i % mod

    def ncr(self, n, r):
        if r < 0 or r > n:
            return 0
        return self.fact[n] * self.inv_fact[r] % self.mod * self.inv_fact[n - r] % self.mod

Why the downward fill works: 1/(i-1)! = i / i!, so invFact[i-1] = invFact[i] · i. Setup is O(n + log p). Our implementation returns 10 for C(5, 2) and 149,033,233 for C(100000, 50000) mod 10⁹+7, matching Python's exact math.comb reduced mod p.

Combinatorics Patterns That Recur

Grid paths

Unique Paths (LC 62): any path from top-left to bottom-right of an m × n grid is a sequence of (m-1) downs and (n-1) rights, so the answer is C(m+n-2, m-1). For 3 × 7 that is C(8, 2) = 28. The DP solution is expected first; mentioning the closed form is a strong signal. With obstacles, the closed form no longer applies and you go back to DP.

Catalan numbers

Cn = C(2n, n) / (n + 1): 1, 1, 2, 5, 14, 42, ... They count structurally unique BSTs with n nodes (Unique Binary Search Trees, LC 96), valid parentheses strings with n pairs (the count behind Generate Parentheses), ways to triangulate a polygon and mountain ranges. Recognising "this recurrence is sum dp[i] · dp[n-1-i]" as Catalan lets you answer instantly.

Stars and bars

The number of ways to put n identical items into k distinct boxes is C(n + k - 1, k - 1); if every box needs at least one, C(n - 1, k - 1). It appears in "count non-negative integer solutions" problems and in distributing candies variants.

Inclusion-exclusion

"Count numbers up to n divisible by a or b" is n/a + n/b - n/lcm(a,b). Combined with binary search on the answer, this solves Nth Magical Number (LC 878) and Ugly Number III (LC 1201). Generally: add singles, subtract pairs, add triples.

Pigeonhole

n + 1 items in n boxes force a collision. It is the reason Find the Duplicate Number (LC 287) has a duplicate at all, and why "subarray sum divisible by k" problems always have an answer when the array is longer than k (two prefix sums share a remainder).

Classic Math Interview Problems and the Tool Each Needs

Factorial Trailing Zeroes deserves a sentence: zeros come from factors of 10 = 2 × 5, and factors of 2 are always more plentiful, so count factors of 5. Numbers like 25 contribute two, which is why you add n/25, n/125 and so on. For n = 100 the answer is 20 + 4 = 24.

How Math Shows Up in Interviews and OAs

Pure math questions are more common in online assessments (HackerRank, HackerEarth, Codility-style tests used by many Indian product companies and banks) than in onsite rounds. In live interviews, math usually appears as a component: a DP whose answer is taken mod 10⁹+7, a binary search whose bounds need overflow care, a hash key that must be a reduced fraction.

What interviewers probe:

• Overflow awareness. "What happens if n is 10⁹?" Know your type limits: 2³¹ - 1 ≈ 2.1 × 10⁹, 2⁶³ - 1 ≈ 9.2 × 10¹⁸.
• Proof of complexity. Why is Euclid logarithmic? Why does the sieve start at i²?
• Exactness. Using double for slopes or square roots is a red flag when an integer method exists.
• Closed form vs DP. For Unique Paths or Unique BSTs, offering both and explaining the trade-off (closed form is faster but breaks with obstacles or constraints) shows depth.

For quant-leaning firms (DE Shaw, Goldman Sachs, Tower-style shops), expect more probability and combinatorics; the company guides such as DE Shaw interview preparation list what is commonly reported.

Common Math Mistakes in Coding Rounds

1. Reducing only at the end. Overflow happens in the middle. Reduce after every multiplication.
2. Negative remainders. (a - b) % MOD can be negative in C++/Java. Add MOD before the final %.
3. Dividing under a modulus. Use the inverse. And remember the inverse only exists when gcd(b, m) = 1.
4. lcm = a * b / gcd. The product overflows first; use a / gcd * b.
5. Floating-point sqrt in loops. for (i = 2; i <= sqrt(n); i++) can miss by one due to rounding; use i * i <= n with 64-bit i.
6. Sieve inner loop from 2·i. Correct but slower; from i·i is the standard. And i * i in int overflows for i above 46,340.
7. Forgetting 0 and 1 in primality checks and sieves.
8. Pow with INT_MIN. Negating overflows.
9. Python slowness. Pure-Python loops over 10⁷ elements time out; use slice assignment, built-in pow and math.comb.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.