Chinese Remainder Theorem (CRT)
CRT solves systems of congruences: given x ≡ ai (mod mi) where mi are pairwise coprime, there exists a unique solution modulo M = m1 * m2 * … * mk.
Solution formula: x = sum(ai * Mi * yi) mod M, where Mi = M / mi and yi is the modular inverse of Mi mod mi.
def extended_gcd(a, b):
if b == 0:
return a, 1, 0
g, x, y = extended_gcd(b, a % b)
return g, y, x - (a // b) * y
def mod_inverse(a, m):
g, x, _ = extended_gcd(a % m, m)
if g != 1:
raise ValueError("Inverse does not exist")
return x % m
def crt(remainders, moduli):
"""Chinese Remainder Theorem solver.
Returns x such that x == r (mod m) for each (r, m) in zip(remainders, moduli).
Assumes moduli are pairwise coprime.
"""
M = 1
for m in moduli:
M *= m
x = 0
for a, m in zip(remainders, moduli):
Mi = M // m
yi = mod_inverse(Mi, m)
x += a * Mi * yi
return x % M
# Example: x == 2 (mod 3), x == 3 (mod 5), x == 2 (mod 7)
# Answer: 23
print(crt([2, 3, 2], [3, 5, 7])) # 23
Use cases: LC 1796 (Second Largest Digit in a String), clock synchronization problems where two clocks align at periods p1 and p2 – find when they next align simultaneously.
Euler’s Totient Function phi(n)
phi(n) counts integers in [1, n] that are coprime to n.
- phi(p) = p – 1 for prime p
- phi(p^k) = p^(k-1) * (p – 1)
- Multiplicative: phi(mn) = phi(m) * phi(n) when gcd(m, n) = 1
def euler_totient(n):
"""Compute phi(n) via prime factorization."""
result = n
p = 2
temp = n
while p * p 1:
result -= result // temp
return result
def totient_sieve(n):
"""Compute phi(i) for all i in [1, n] using sieve."""
phi = list(range(n + 1))
for i in range(2, n + 1):
if phi[i] == i: # i is prime
for j in range(i, n + 1, i):
phi[j] -= phi[j] // i
return phi
# Modular inverse using Euler theorem: a^(phi(m)-1) mod m when gcd(a,m)=1
def mod_inverse_euler(a, m):
return pow(a, euler_totient(m) - 1, m)
Fermat’s Little Theorem (special case): when m is prime, a^(m-1) ≡ 1 (mod m), so a^(-1) ≡ a^(m-2) (mod m). Use pow(a, m-2, m) for fast modular inverse when m is prime.
Digit DP
Digit DP counts numbers in [0, N] satisfying some property defined on their digits. The key insight is processing digits from most significant to least significant with a tight flag indicating whether the current prefix is still bounded by N.
Template state: (position, tight, problem-specific state)
from functools import lru_cache
def count_numbers(N, K):
"""Count numbers in [0, N] where digit sum == K."""
digits = list(map(int, str(N)))
n = len(digits)
@lru_cache(maxsize=None)
def dp(pos, tight, current_sum, started):
if pos == n:
return 1 if current_sum == K else 0
limit = digits[pos] if tight else 9
result = 0
for d in range(0, limit + 1):
new_started = started or d > 0
new_sum = (current_sum + d) if new_started else 0
if new_sum > K:
break
result += dp(pos + 1, tight and d == limit, new_sum, new_started)
return result
return dp(0, True, 0, False)
def count_no_adjacent_same(N):
"""Count numbers in [1, N] with no two adjacent identical digits."""
digits = list(map(int, str(N)))
n = len(digits)
@lru_cache(maxsize=None)
def dp(pos, tight, prev_digit, started):
if pos == n:
return 1 if started else 0
limit = digits[pos] if tight else 9
result = 0
for d in range(0, limit + 1):
if started and d == prev_digit:
continue
result += dp(pos + 1, tight and d == limit, d, started or d > 0)
return result
return dp(0, True, -1, False)
def count_divisible_by_k(N, K):
"""Count numbers in [1, N] divisible by K."""
digits = list(map(int, str(N)))
n = len(digits)
@lru_cache(maxsize=None)
def dp(pos, tight, remainder, started):
if pos == n:
return 1 if (started and remainder == 0) else 0
limit = digits[pos] if tight else 9
result = 0
for d in range(0, limit + 1):
new_rem = (remainder * 10 + d) % K if (started or d > 0) else 0
result += dp(pos + 1, tight and d == limit, new_rem, started or d > 0)
return result
return dp(0, True, 0, False)
Tight flag: when tight=True, the digit at this position can be at most digits[pos]. When tight=False, any digit 0-9 is allowed. Once we pick a digit less than the limit, tight becomes False for all subsequent positions.
Integer Factorization and Smallest Prime Factor Sieve
Trial division is O(sqrt(n)) per number. For repeated factorization queries, precompute the Smallest Prime Factor (SPF) sieve to factor any n in O(log n) after O(n log log n) preprocessing.
import math
def factorize_trial(n):
"""Trial division factorization - O(sqrt(n))."""
factors = {}
d = 2
while d * d 1:
factors[n] = factors.get(n, 0) + 1
return factors
def spf_sieve(limit):
"""Smallest Prime Factor sieve - O(n log log n) preprocessing."""
spf = list(range(limit + 1))
for i in range(2, int(math.sqrt(limit)) + 1):
if spf[i] == i: # i is prime
for j in range(i * i, limit + 1, i):
if spf[j] == j:
spf[j] = i
return spf
def factorize_spf(n, spf):
"""Factorize n using precomputed SPF - O(log n)."""
factors = {}
while n > 1:
p = spf[n]
while n % p == 0:
factors[p] = factors.get(p, 0) + 1
n //= p
return factors
# Pollard rho is O(n^(1/4)) per factor - use for n > 10^12
# Available in sympy: sympy.factorint(n)
# Example: factor all numbers up to 10^6
spf = spf_sieve(10**6)
print(factorize_spf(360, spf)) # {2: 3, 3: 2, 5: 1}
When to use what:
- Single number, n < 10^9: trial division
- Many queries for n < 10^6: SPF sieve
- Very large n (10^12+): Pollard’s rho O(n^(1/4))
Frequently Asked Questions
When should I use the Chinese Remainder Theorem in coding interviews?
Use CRT when you have a system of modular congruences with pairwise coprime moduli and need to find a unique solution. Common patterns: combining results from multiple hash functions, clock synchronization problems where two events with periods p1 and p2 must align, and problems involving multiple independent modular constraints.
How do I compute modular inverse efficiently in Python?
For prime modulus m, use pow(a, m-2, m) via Fermat’s little theorem – O(log m). For general modulus, use the extended Euclidean algorithm or pow(a, euler_totient(m)-1, m). Python 3.8+ also supports pow(a, -1, m) as a built-in for modular inverse.
What is the tight flag in Digit DP and why is it necessary?
The tight flag tracks whether the current digit prefix is still bounded by the upper limit N. When tight=True, the next digit can be at most digits[pos] (the corresponding digit of N). When tight=False, any digit 0-9 is valid. Without this flag, you would overcount numbers exceeding N.
What is the time complexity advantage of the smallest prime factor sieve?
The SPF sieve preprocesses in O(n log log n) time and O(n) space. After preprocessing, factorizing any number k <= n takes O(log k) time by repeatedly dividing by spf[k]. This beats trial division's O(sqrt(k)) per query when you need to factorize many numbers.
How does Euler’s totient function relate to modular arithmetic?
Euler’s theorem states: a^phi(n) ≡ 1 (mod n) when gcd(a,n)=1. This means a^(-1) ≡ a^(phi(n)-1) (mod n), giving a formula for modular inverse. When n is prime, phi(n)=n-1, recovering Fermat’s little theorem. The totient is also used in RSA: e*d ≡ 1 (mod phi(n)).
See also: Meta Interview Prep: Number Theory and Math Problems
See also: Coinbase Interview Prep: Algorithms and Number Theory