GCD and LCM
Euclidean algorithm: gcd(a,b) = gcd(b, a%b), base case gcd(a,0) = a. Time O(log min(a,b)). LCM: lcm(a,b) = a*b // gcd(a,b) (divide before multiply to avoid overflow).
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 prevent overflow
LC 1979 (GCD of array), LC 2413 (smallest multiple), LC 365 (water jug problem — Bezout’s identity: can measure x liters iff x is divisible by gcd(a,b)).
Prime Numbers: Sieve of Eratosthenes
Find all primes up to N in O(N log log N) time, O(N) space. Mark composites by iterating multiples of each prime.
def sieve(n):
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(n**0.5) + 1):
if is_prime[i]:
for j in range(i*i, n+1, i):
is_prime[j] = False
return [i for i in range(2, n+1) if is_prime[i]]
Start inner loop at i*i (smaller multiples already marked). LC 204 (Count Primes). For single primality test: trial division up to sqrt(n), O(sqrt(n)).
Prime Factorization
Factorize n in O(sqrt(n)): divide by 2, then try odd divisors up to sqrt(n). Any remaining factor > 1 is prime.
def prime_factors(n):
factors = []
d = 2
while d * d 1:
factors.append(n)
return factors
LC 2507 (smallest value after operations), LC 952 (largest component by common factor — build graph from shared prime factors).
Modular Arithmetic
For large numbers, apply mod at each step: (a + b) % m = ((a % m) + (b % m)) % m. Same for multiplication. For division: use modular inverse — a/b mod m = a * pow(b, m-2, m) mod m (Fermat’s little theorem, valid when m is prime).
MOD = 10**9 + 7 # prime, standard in competitive programming # Fast modular exponentiation (built into Python) result = pow(base, exp, MOD) # O(log exp) # Modular inverse (when MOD is prime) inv_b = pow(b, MOD - 2, MOD)
Apply mod proactively in DP to prevent integer overflow (Python handles big ints natively but mod is still required for the answer). LC 509 (Fibonacci mod), LC 1922 (count good numbers).
Fast Power (Binary Exponentiation)
Compute base^exp in O(log exp) using repeated squaring: if exp is even, base^exp = (base^2)^(exp/2); if odd, base^exp = base * base^(exp-1).
def power(base, exp, mod):
result = 1
base %= mod
while exp > 0:
if exp % 2 == 1:
result = result * base % mod
base = base * base % mod
exp //= 2
return result
Python’s built-in pow(base, exp, mod) does this natively. Useful in LC 50 (Pow(x,n)), cryptography problems.
Combinatorics: nCr mod p
Precompute factorials and inverse factorials for O(1) nCr queries:
MOD = 10**9 + 7
MAX = 10**5 + 1
fact = [1] * MAX
for i in range(1, MAX):
fact[i] = fact[i-1] * i % MOD
inv_fact = [1] * MAX
inv_fact[MAX-1] = pow(fact[MAX-1], MOD-2, MOD)
for i in range(MAX-2, -1, -1):
inv_fact[i] = inv_fact[i+1] * (i+1) % MOD
def nCr(n, r):
if r n: return 0
return fact[n] * inv_fact[r] % MOD * inv_fact[n-r] % MOD
LC 62 (unique paths), LC 1569 (reorder routes), LC 1866 (rearrange sticks).
When to Use Number Theory
- GCD/LCM: fraction simplification, water jug, divisibility conditions
- Sieve: count primes, find prime factors in bulk, grouping by prime factors
- Modular arithmetic: any DP with “return answer mod 10^9+7”, combinations, large exponents
- Binary exponentiation: matrix exponentiation for linear recurrences (Fibonacci in O(log n))
Google coding interviews frequently test number theory and math patterns. See common questions for Google interview: number theory and math coding problems.
Meta coding interviews test number theory, GCD, and modular arithmetic. See patterns for Meta interview: number theory and combinatorics problems.
Atlassian coding rounds include number theory problems. Review GCD, primes, and mod patterns for Atlassian interview: math and number theory coding problems.