Number Theory

Type: Math / Theory LeetCode tag size: ~80 problems — core algorithms, main patterns, key complexities covered.

---

Core Concepts

Divisibility — a divides b (written a | b) iff b % a == 0. Every integer divides 0.

Prime — integer > 1 with exactly two divisors: 1 and itself. 1 is not prime.

Composite — integer > 1 with a divisor other than 1 and itself. Every composite has a prime factor ≤ √n.

GCD (Greatest Common Divisor) — largest integer dividing both a and b. gcd(a, 0) = a; gcd(0, 0) is undefined.

LCM (Least Common Multiple) — smallest positive integer divisible by both: lcm(a, b) = a * b // gcd(a, b). Compute via GCD to avoid overflow.

Modular arithmetic — (a + b) % m = ((a % m) + (b % m)) % m; same for multiplication. Division requires modular inverse.

Modular inverse — x such that a * x ≡ 1 (mod m). Exists iff gcd(a, m) = 1. For prime m, equals a^(m−2) % m (Fermat's little theorem).

Euler's totient φ(n) — count of integers in [1, n] coprime to n. For prime p: φ(p) = p − 1. Multiplicative: φ(ab) = φ(a)φ(b) when gcd(a, b) = 1.

Fundamental theorem of arithmetic — every integer > 1 factors uniquely into primes (up to order).

Coprime — gcd(a, b) = 1; no shared prime factors.

Trailing zeros of n! — count of 5s in prime factorization of n! (5s are limiting factor over 2s): ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + …

Perfect square — integer whose square root is an integer. Count of divisors is odd iff perfect square.

---

Types / Variants

---

Key Algorithms

Euclidean Algorithm (GCD)

Repeatedly replace (a, b) with (b, a % b) until b = 0; gcd = a. Correct because gcd(a, b) = gcd(b, a % b).

Time: O(log min(a, b)). Space: O(1) iterative, O(log min) recursive stack.

def gcd(a, b): return a if b == 0 else gcd(b, a % b)

Extended Euclidean Algorithm

Finds x, y such that ax + by = gcd(a, b). Used to compute modular inverse when gcd(a, m) = 1 → x % m is the inverse. Time: O(log min(a, b)).

Sieve of Eratosthenes

Marks all composites up to n by crossing off multiples of each prime. Start marking from p² (all smaller multiples already crossed). After the sieve, is_prime[i] is True iff i is prime.

Time: O(n log log n). Space: O(n).

sieve = [True] * (n + 1)
sieve[0] = sieve[1] = False
for p in range(2, int(n**0.5) + 1):
    if sieve[p]:
        for mul in range(p*p, n+1, p): sieve[mul] = False

Trial Division (Primality Test / Prime Factorization)

Test divisors from 2 to √n. If no divisor found, n is prime. For factorization, repeatedly divide out each prime factor.

Time per number: O(√n).

def smallest_prime_factor(n):
    for p in range(2, int(n**0.5) + 1):
        if n % p == 0: return p
    return n  # n is prime

Smallest Prime Factor Sieve (SPF)

Precompute smallest prime factor for every number ≤ n. Factorization of any x ≤ n takes O(log x) by repeatedly dividing by spf[x]. Build: O(n log log n) like standard sieve. Useful when factorizing many numbers.

Fast Modular Exponentiation (Binary Exponentiation)

Compute base^exp % mod in O(log exp) by squaring: if exp is odd, multiply result by base; always square base and halve exp.

def pow_mod(base, exp, mod):
    result = 1
    base %= mod
    while exp:
        if exp & 1: result = result * base % mod
        base = base * base % mod
        exp >>= 1
    return result

Python's pow(base, exp, mod) uses this — always prefer it over manual implementation.

Modular Inverse

• Prime modulus (Fermat): inv(a) = pow(a, mod-2, mod) — requires mod is prime and gcd(a, mod) = 1. Time: O(log mod).
• General modulus: Extended Euclidean. Time: O(log mod).
• Precompute 1..n inverses: inv[i] = -(mod // i) * inv[mod % i] % mod with inv[1] = 1. O(n) total.

Divisor Enumeration

Iterate i from 1 to √n; i and n // i are both divisors iff n % i == 0. Time: O(√n).

Sieve of Smallest Prime Factors + Bulk Factorization

Build SPF sieve; for each query x, factor as while x > 1: factor spf[x], x //= spf[x]. Amortized O(log n) per query after O(n log log n) precomputation.

---

Advanced Techniques

Chinese Remainder Theorem (CRT)

Solves: system of congruences x ≡ r_i (mod m_i) where all m_i are pairwise coprime. Mechanism: construct a combined modulus M = Π m_i; for each equation compute M_i = M / m_i and its inverse mod m_i; sum contributions. When to use over simpler alternatives: only when you have multiple simultaneous congruences. Not needed when a single % m suffices. Time: O(k log M) for k equations.

Euler's Totient Function

Solves: count of integers in [1, n] coprime to n; exponent in Euler's theorem a^φ(n) ≡ 1 (mod n) for gcd(a,n)=1. Mechanism: φ(n) = n * Π (1 − 1/p) over prime factors p of n. Compute during factorization. When to use: Euler's theorem generalises Fermat's little theorem to non-prime moduli. Use when mod is not prime and you need repeated exponentiation. Time: O(√n) per number; O(n log log n) for sieve version.

Precomputed Factorials and Inverse Factorials (Combinatorics mod p)

Solves: C(n, k) % p for large n, k with prime p. Mechanism: precompute fact[i] = i! % p and inv_fact[i] using modular inverse; C(n,k) = fact[n] * inv_fact[k] * inv_fact[n-k] % p. When to use over simpler alternatives: use only when p is prime and n < p. Use Lucas' theorem when n ≥ p. Time: O(n) precomputation, O(1) per query.

See math.md for combinatorics coverage.

---

Problem Taxonomy

By Problem Category

Problem Signal → Technique

---

Common Patterns

---

Edge Cases & Pitfalls

• n = 0 or n = 1 in primality checks. Neither is prime; naïve loops starting at 2 may incorrectly label them prime or throw index errors. Always guard if n < 2: return False.

• Perfect square check with float sqrt. int(n**0.5)**2 == n fails for large n (float precision). Use isqrt(n)**2 == n (Python 3.8+) for exact integer square root.

• Overflow in LCM. a * b // gcd(a, b) overflows when a * b exceeds 64-bit range. In Python this is not an issue; in C++/Java compute a // gcd(a, b) * b instead.

• Modular inverse requires coprimality. pow(a, mod-2, mod) silently returns a wrong answer when gcd(a, mod) != 1. Verify the condition or use extended GCD with a validity check.

• Sieve off-by-one. Allocating sieve = [True] * n misses index n. Use n + 1 to include n.

• Starting sieve crossing at p² vs. 2p. Starting at 2p is correct but redundant; p² is the first unmarked multiple. Either is correct; p² is faster.

• Power of 3 / power of X check. Repeatedly dividing by X until not divisible, then checking == 1, is correct. 3^19 = 1162261467 fits int32; checking 1162261467 % n == 0 only works for power of 3 if n > 0.

• GCD(0, 0) is undefined. Python's math.gcd(0, 0) returns 0; do not rely on this as a meaningful GCD.

• Factorization loop termination. After dividing out all factors ≤ √n, if n > 1 the remaining n is itself prime — always emit it.

• Digit extraction order. n % 10 gives the least significant digit; for problems needing most-significant-first, extract all digits then reverse, or use string conversion.

---

Implementation Notes

• math.gcd(a, b) in Python 3.5+ handles non-negative integers; math.gcd in 3.9+ accepts more than two arguments.
• pow(base, exp, mod) is a Python builtin — O(log exp), handles mod correctly, never overflows.
• math.isqrt(n) (Python 3.8+) returns exact integer square root; safer than int(n**0.5) for large n.
• math.lcm(a, b) available in Python 3.9+; otherwise a * b // math.gcd(a, b).
• functools.reduce(math.gcd, iterable) computes GCD of the whole list.
• Sieve array of booleans: use bytearray(n+1) instead of a list for ~8× less memory; index access is identical.
• Python integers don't overflow, but explicit % mod is still required to keep values manageable for pow and multiplication.
• divmod(a, b) returns (quotient, remainder) in one call — useful in digit-extraction loops.

---

Cross-Topic Relations

---

Interview Reference

Must-Know Problems

Primality & Primes

• Count Primes (LC 204) — Sieve of Eratosthenes
• Closest Divisors (LC 1362) — factorization to √n
• Four Divisors (LC 1390) — enumerate divisors efficiently

GCD / LCM

• Find Greatest Common Divisor of Array (LC 1979)
• Smallest Even Multiple (LC 2413)
• Three Divisors (LC 1952) — check if divisor count == 3 → perfect square of prime

Modular Arithmetic / Fast Power

• Pow(x, n) (LC 50) — binary exponentiation
• Super Pow (LC 372) — modular exponentiation with large exponent
• Kth Largest XOR Coordinate Value (not directly, but fast pow pattern)

Digit-Based

• Trailing Zeroes (LC 172) — count 5s in n!
• Happy Number (LC 202) — cycle detection on digit sum
• Self Dividing Numbers (LC 728)
• Digit Sum in the Range (LC 1085 variant)

Sequences & Divisors

• Ugly Number II (LC 264) — three-pointer DP
• Super Ugly Number (LC 313) — generalised to k primes
• Count Integers With Even Digit Sum (LC 2180)
• 2 Keys Keyboard (LC 651) — find optimal factorization

Harder

• Broken Calculator (LC 991) — greedy with reverse ops; GCD insight
• Minimum Number of Operations to Make Array Continuous (LC 2009) — sorting + sliding window on divisibility
• Count Ways to Make Array With Product (LC 1735) — combinatorics mod prime; precompute factorials

Clarification Questions to Ask

• Value ranges: can inputs be 0 or negative? (affects GCD, primality checks)
• Is the modulus always prime? (affects which inverse method applies)
• "Prime factors" — does the problem mean distinct primes or with multiplicity?
• "Divisors" — does it include 1 and n themselves?
• Are duplicate answers allowed, or is the result a set?

Common Interview Mistakes

• Using float square root for primality or perfect-square checks — imprecise for large inputs; use isqrt.
• Forgetting % mod after multiplication inside a loop — intermediate products silently grow.
• Trial division loop goes to n instead of √n — O(n) instead of O(√n).
• Counting 2s instead of 5s for trailing zeros in n! — 2s are always more abundant.
• Missing the remaining prime factor after the trial-division loop (the if n > 1: factors.append(n) step).
• Using gcd(a, b) = a % b directly (misremembering the algorithm) — correct form is gcd(b, a % b).

Typical Follow-Up Escalations

• "Now find the k-th prime" → sieve up to a bound estimated by prime number theorem (~k ln k), or segmented sieve.
• "Now handle multiple queries for C(n, k) % p" → precompute factorial and inverse factorial arrays.
• "Now the modulus is not prime" → switch from Fermat to extended Euclidean for modular inverse; CRT if moduli are given.
• "Factorize numbers up to 10^6 for 10^5 queries" → SPF sieve precomputation, O(log n) per factorization query.
• "n can be up to 10^18" → Miller-Rabin probabilistic primality test; Pollard's rho factorization.