Math & Number Theory

GCD, primes, fast exponentiation, modular arithmetic and careful digit handling.

Math questions in coding rounds aren't about advanced theory. They test whether you know a few standard tools (GCD, primes, fast exponentiation, modular arithmetic) and whether you handle overflow, signs and edge cases carefully. Many are really "careful implementation" questions in disguise.

GCD and LCM

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

def lcm(a, b):
    return a // gcd(a, b) * b      # divide first to keep numbers small

GCD shows up in places you might not expect: *GCD of Strings*, the water jug problem (target reachable ⇔ divisible by gcd), counting points on a line (store the slope as a reduced fraction (dy/g, dx/g) rather than a float), and *Nth Magical Number* (inclusion–exclusion with the LCM).

Primes

Is n prime? Trial division up to √n: O(√n).
All primes up to n: the Sieve of Eratosthenes, O(n log log n).

def count_primes(n):
    if n < 3:
        return 0
    is_prime = [True] * n
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if is_prime[i]:
            is_prime[i * i::i] = [False] * len(range(i * i, n, i))
    return sum(is_prime)

Start crossing out at i², because every smaller multiple was already crossed out by a smaller prime.

Fast exponentiation

Compute xⁿ in O(log n) by squaring: x¹³ = x⁸ · x⁴ · x¹, following the bits of 13.

def power(x, n, mod=None):
    if n < 0:
        x, n = 1 / x, -n
    result = 1
    while n:
        if n & 1:
            result = result * x if mod is None else result * x % mod
        x = x * x if mod is None else x * x % mod
        n >>= 1
    return result

Modular arithmetic

When a question says "return the answer modulo 10⁹ + 7", the answer is huge. Apply the modulus after every addition and multiplication, not just at the end:

(a + b) % m and (a * b) % m are safe to apply step by step.
For subtraction, add m before taking the result: (a - b + m) % m.
For division, multiply by the modular inverse instead: pow(b, m - 2, m) when m is prime (Fermat's little theorem).

In Python, integers never overflow, but carrying enormous numbers through a loop is slow. In Java and C++, a product of two values near 10⁹ overflows 32 bits, so cast to long before multiplying.

Digits and number formatting

A large share of "math" questions are really string and digit handling:

Reverse an integer / string to integer (atoi): handle the sign, leading whitespace, invalid characters and 32-bit overflow. Check for overflow *before* multiplying by 10.
Integer ↔ Roman numerals, integer → English words: table-driven code with value/symbol pairs, from largest to smallest.
Excel column titles: base 26, but with no zero digit. Subtract 1 before each divmod.
Add or multiply numbers stored as strings: grade-school arithmetic, digit by digit, with a carry.

def column_title(n):
    out = []
    while n:
        n, r = divmod(n - 1, 26)
        out.append(chr(ord("A") + r))
    return "".join(reversed(out))

Counting and combinatorics

Trailing zeroes of n!: count the factors of 5: n//5 + n//25 + n//125 + …
nCk mod p: precompute factorials and inverse factorials.
The kth permutation: a factorial number system. Each digit is chosen by dividing k by (n−1)!.

Randomness

Reservoir sampling: pick a uniformly random item from a stream of unknown length. Keep the ith item with probability 1/i.
Shuffle (Fisher–Yates): for i from n−1 down to 1, swap a[i] with a[randint(0, i)].

[!INTERVIEW] Name the edge cases before you code "Zero, negative numbers, the minimum 32-bit integer (whose absolute value doesn't fit), and overflow." Listing these up front shows the carefulness these questions exist to test.

[!TIP] Practice Pow(x, n) · Count Primes · String to Integer (atoi) · Reverse Integer · Integer to Roman · Multiply Strings · Excel Sheet Column Title · Factorial Trailing Zeroes · Max Points on a Line · Reservoir Sampling