Math & Number Theory for Coding

The math interviews actually test: GCD/Euclid, modular arithmetic and the 1e9+7 convention, fast exponentiation, the sieve and primality, nCr mod p, and the overflow traps — the toolkit behind half of LeetCode's medium math tags.

Why a math page

A surprising share of "array" problems are number theory wearing a costume: anything with "return the answer modulo 1e9+7", counting problems, digit problems, or "is this reachable" GCD puzzles. None of it is research math — it's six reusable tools. Heaviest at Google, Amazon, Adobe, and quant/HFT screens (Two Sigma, Jane Street, Bloomberg).

💡 Visualizing the math concepts:

GCD (Euclidean Algorithm): Imagine you want to tile a floor of size $a \times b$ using the largest possible square tiles. If you lay down square tiles of size $b \times b$, you're left with a smaller rectangular strip of size $b \times (a \bmod b)$. Finding the GCD is just repeating this tiling process on the remaining strip until no space is left.

Modular Arithmetic (Clock Math): Think of modulo like a 12-hour clock. If it's 10 o'clock and you wait 5 hours, it becomes 3 o'clock, not 15 o'clock. The numbers loop around. The mod is just the circumference of the circle.

Binary Exponentiation (Fast Powering): Imagine calculating $2^8$. Instead of multiplying 2 by itself eight times ($2 \times 2 \times 2 \dots$), you square it three times: $2 \rightarrow 4 \rightarrow 16 \rightarrow 256$. By splitting the exponent in half at each step, you turn a tedious linear task into a logarithmic sprint.

Complexity of Core Operations

Operation	Time Complexity	Space Complexity	Best Use Case
GCD / LCM (Euclidean)	O(log(min(A, B)))	O(1) iterative, O(log(min(A, B))) recursive	Simplify fractions, check grid reachability
Fast Exponentiation	O(log N)	O(1)	High-power modular exponentiation, modular inverse
Trial Division	O(sqrt(X))	O(1)	Single primality test
Sieve of Eratosthenes	O(N log log N)	O(N)	Finding all prime numbers up to N
Combinatorics mod p	O(R log P)	O(1)	Path counting on grids, combinations mod prime

GCD & LCM (Euclid)

Python

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

def lcm(a, b):
    return a // gcd(a, b) * b     # divide FIRST to avoid overflow

Java

// Java — GCD & LCM
public long gcd(long a, long b) {
    while (b != 0) {
        long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

public long lcm(long a, long b) {
    if (a == 0 || b == 0) return 0;
    return (a / gcd(a, b)) * b;   // divide FIRST to avoid overflow
}

C++

// C++ — GCD & LCM
long long gcd(long long a, long long b) {
    while (b) {
        long long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

long long lcm(long long a, long long b) {
    if (a == 0 || b == 0) return 0;
    return (a / gcd(a, b)) * b;   // divide FIRST to avoid overflow
}

GCD shows up in "reduce a fraction", "can I tile/reach with steps p and q" (reachable iff the target is a multiple of gcd(p, q)), and string-period problems.

Watch the descent: each row replaces (a, b) with (b, a mod b), and the numbers shrink startlingly fast — that's the O(log n) right there.

Euclid's algorithm — gcd(a, b)time O(log min(a, b))space O(1)

aba mod b

1/5Euclid's algorithm: gcd(a, b) = gcd(b, a mod b). Keep replacing (a, b) with (b, a mod b) until b hits 0 — the last nonzero value is the gcd. Start: a = 48, b = 18.

a = 48b = 18

Modular arithmetic — the `1e9+7` convention

Counting answers blow past 64 bits, so problems ask for the result mod a large prime (1_000_000_007). The rules that survive the mod:

(a + b) % m, (a − b + m) % m (add m so it stays non-negative), (a * b) % m — all fine.
Division does not distribute over mod. To compute a / b mod m you need the modular inverse of b. When m is prime, Fermat's little theorem gives inverse(b) = b^(m−2) mod m.

Python

MOD = 1_000_000_007
def inv(b):           # modular inverse via Fermat (m is prime)
    return pow(b, MOD - 2, MOD)

Fast exponentiation (binary exp)

pow(x, n) in O(log n) by squaring — and the engine behind the modular inverse above:

Python

def fast_pow(x, n, mod=None):
    result = 1
    while n > 0:
        if n & 1: result = result * x % mod if mod else result * x
        x = x * x % mod if mod else x * x
        n >>= 1
    return result

Java

// Java — Fast Exponentiation
public long fastPow(long x, long n, long mod) {
    long result = 1;
    x %= mod;
    if (x < 0) x += mod;
    while (n > 0) {
        if ((n & 1) == 1) result = (result * x) % mod;
        x = (x * x) % mod;
        n >>= 1;
    }
    return result;
}

C++

// C++ — Fast Exponentiation
long long fastPow(long long x, long long n, long long mod) {
    long long result = 1;
    x %= mod;
    if (x < 0) x += mod;
    while (n > 0) {
        if (n & 1) result = (result * x) % mod;
        x = (x * x) % mod;
        n >>= 1;
    }
    return result;
}

(Python's built-in pow(x, n, mod) already does this — but interviewers ask you to derive it.)

Step through the bits of the exponent: the base squares every row, and only gets folded into the result where the exponent bit is 1 — O(log n) rows instead of n multiplications.

Fast exponentiation — aⁿ by squaringtime O(log n)space O(1)

kbitbaseresult

1/6Compute 3^13 by squaring. Write the exponent in binary: 13 = 1101₂. Walk its bits from least significant — square the base every step, and fold it into the result only where the bit is 1. "base" is a raised to 2^k.

a = 3n = 13n in binary = 1101

base (2–9)exponent (1–16)

Primes — sieve & primality

Python

def sieve(n):                      # all primes ≤ n, O(n log log n)
    is_p = [True] * (n + 1)
    is_p[0] = is_p[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if is_p[i]:
            for j in range(i * i, n + 1, i):   # start at i*i; smaller multiples already marked
                is_p[j] = False
    return [i for i, p in enumerate(is_p) if p]

def is_prime(x):                   # single number: trial division to √x
    if x < 2: return False
    i = 2
    while i * i <= x:
        if x % i == 0: return False
        i += 1
    return True

Java

// Java — Sieve of Eratosthenes & Trial Division
import java.util.ArrayList;
import java.util.List;

public List<Integer> sieve(int n) {
    boolean[] is_p = new boolean[n + 1];
    java.util.Arrays.fill(is_p, true);
    if (n >= 0) is_p[0] = false;
    if (n >= 1) is_p[1] = false;
    for (int i = 2; i * i <= n; i++) {
        if (is_p[i]) {
            for (int j = i * i; j <= n; j += i) {
                is_p[j] = false;
            }
        }
    }
    List<Integer> primes = new ArrayList<>();
    for (int i = 2; i <= n; i++) {
        if (is_p[i]) primes.add(i);
    }
    return primes;
}

public boolean isPrime(long x) {
    if (x < 2) return false;
    for (long i = 2; i * i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}

C++

// C++ — Sieve of Eratosthenes & Trial Division
#include <vector>

std::vector<int> sieve(int n) {
    std::vector<bool> is_p(n + 1, true);
    if (n >= 0) is_p[0] = false;
    if (n >= 1) is_p[1] = false;
    for (int i = 2; i * i <= n; i++) {
        if (is_p[i]) {
            for (int j = i * i; j <= n; j += i) {
                is_p[j] = false;
            }
        }
    }
    std::vector<int> primes;
    for (int i = 2; i <= n; i++) {
        if (is_p[i]) primes.push_back(i);
    }
    return primes;
}

bool isPrime(long long x) {
    if (x < 2) return false;
    for (long long i = 2; i * i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}

Combinatorics mod p

nCr mod p = factorials times inverse factorials:

Python

def nCr_mod(n, r, mod=1_000_000_007):
    if r < 0 or r > n: return 0
    num = den = 1
    for i in range(r):
        num = num * (n - i) % mod
        den = den * (i + 1) % mod
    return num * pow(den, mod - 2, mod) % mod

Java

// Java — Combinatorics mod p (nCr mod p)
public long nCrMod(int n, int r, long mod) {
    if (r < 0 || r > n) return 0;
    long num = 1;
    long den = 1;
    for (int i = 0; i < r; i++) {
        num = (num * (n - i)) % mod;
        den = (den * (i + 1)) % mod;
    }
    return (num * fastPow(den, mod - 2, mod)) % mod;
}

C++

// C++ — Combinatorics mod p (nCr mod p)
long long nCrMod(int n, int r, long long mod) {
    if (r < 0 || r > n) return 0;
    long long num = 1;
    long long den = 1;
    for (int i = 0; i < r; i++) {
        num = (num * (n - i)) % mod;
        den = (den * (i + 1)) % mod;
    }
    return (num * fastPow(den, mod - 2, mod)) % mod;
}

Think it through like the interview

Think it through: Pow(x, n)Medium — LeetCode 50 (Amazon, Google, Bloomberg)0/3 stages

PROBLEMImplement pow(x, n) — x to the power n — better than the naive O(n) loop, handling negative n.

1
Why O(n) multiplication is wrong
“n can be ~2 billion. How many multiplications does the naive loop do?”
2
Square and halve — O(log n)
“If x^n = (x^(n/2))², how do I handle odd n, and how many steps is it?”
unlocks after the stage above
3
Negative n and overflow
“What breaks at the boundaries?”
unlocks after the stage above

Overflow is the silent killer

Python integers are unbounded, so these read cleanly — but in Java/C++, a * b for two ints near 10⁹ overflows a 32-bit int before you take the mod. Use 64-bit (long / long long), take the mod after every multiply, and for lcm divide before multiplying. State this; it's a common rejection reason in those languages.

Check yourself

Check yourself0/3 answered

1. Why is taking modular reduction after every arithmetic operation necessary in C++ or Java?

2. Under what condition does Fermat's Little Theorem allow us to compute the modular inverse of b as b^(m-2) mod m?

3. What is the primary benefit of the Sieve of Eratosthenes over Trial Division for checking primes?

Practice — climb the ladder

The skill is spotting the math tool hiding in a word problem — "modulo 1e9+7" means modular arithmetic, "huge exponent" means binary exp, "count primes" means a sieve.

Practice ladder: Math & Number Theory0/11 solved

Climb in order — every rung assumes the one above it. Solve on LeetCode, then tick it here; progress is saved on this device.

Warm-up — SDE-1

the core tools in isolation

Pow(x, n)Medium
Binary exponentiation — square and halve, handle negative n.
Sqrt(x)Easy
Integer sqrt via binary search — no float tricks.
Count PrimesMedium
Sieve of Eratosthenes, start crossing at i*i.
Happy NumberEasy
Digit math + cycle detection.

Core — SDE-2

digit and divisor reasoning

Factorial Trailing ZeroesMedium
Count factors of 5 — the non-brute-force insight.
Excel Sheet Column NumberEasy
Base-26 positional decoding.
Greatest Common Divisor of StringsEasy
Euclid's algorithm applied to string periods.
Ugly Number IIMedium
Multi-pointer merge on prime factors {2,3,5}.

Stretch — SDE-3 / quant

modular and combinatorial finishes

Super PowMedium
Modular exponentiation with the exponent given as a digit array.
Number of Digit OneHard
Digit DP / counting by place value.
Largest Divisible SubsetMedium
Divisibility chains via sort + DP.