Math and Number Theory — Master Recap and Interview Cheatsheet

Math and Number Theory Master Recap#

Complete cheatsheet for number theory algorithms used across all 19 problems in this series.

Algorithm Selection Guide#

Template Library#

MOD = 10**9 + 7
 
# Fast power
def pw(b, e, m=MOD):
    return pow(b, e, m)
 
# Modular inverse (prime modulus only)
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
 
# Factorial table for nCr
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
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
 
# SPF sieve (smallest prime factor for fast factorization)
def spf_sieve(n):
    s = list(range(n + 1))
    for i in range(2, int(n**0.5) + 1):
        if s[i] == i:
            for j in range(i*i, n+1, i):
                if s[j] == j:
                    s[j] = i
    return s

Complexity Summary#

Top 25 Math/Number Theory LeetCode Problems#

Common Pitfalls#

1. Overflow. Use long long in C++; Python handles natively. In LCM always divide first.
2. Float comparison. Use abs(a-b) < 1e-9, not a == b.
3. Fermat inverse. Only valid when modulus is prime — use Extended GCD otherwise.
4. GCD of 0. gcd(0, n) = n — handle carefully in LCM to avoid division by zero.
5. Sieve optimization. Start inner loop at p*p, not 2*p, to avoid redundant work.
6. nCr for large n. Always precompute factorials; never compute inline in a loop.

Interview Mindset#

• Math problems often have O(1) formulas — look for the closed-form pattern first.
• Binary search on the answer works when feasibility is monotone.
• GCD/LCM often unlocks problems involving multiples and divisibility.
• XOR is the tool for parity, single-occurrence detection, and Nim-style games.
• When stuck, try small examples (n=1,2,3,4) and look for patterns in the sequence.

Key Takeaways#

• The Sieve of Eratosthenes generates all primes up to n in O(n log log n) — the inner loop starts at p*p, not 2p.
• GCD via the Euclidean algorithm runs in O(log n) and is the foundation of LCM, modular inverse, and CRT.
• Binary exponentiation computes a^n mod m in O(log n) by squaring at each bit of the exponent.
• Fermat's little theorem gives modular inverse as a^(m-2) mod m, but only when m is prime.
• Precomputing factorials in O(n) enables O(1) nCr queries — essential for combinatorics problems.
• LCM overflow is avoided by dividing before multiplying: a // gcd(a, b) * b.
• SPF (smallest prime factor) sieve enables O(log n) factorization of any number after O(n log log n) preprocessing.