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))
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”How does the Euclidean algorithm compute GCD?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”The Euclidean algorithm: gcd(a, b) = gcd(b, a % b), base case gcd(a, 0) = a. Each step replaces the larger number with the remainder, reducing the problem size. Time complexity: O(log min(a,b)) — the number of steps is bounded by the number of digits. Implementation: def gcd(a, b): while b: a, b = b, a % b; return a. For LCM: lcm(a, b) = a // gcd(a, b) * b (divide first to prevent overflow). Applications in interviews: LC 1979 (find GCD of array — iteratively apply gcd), LC 365 (water jug — can measure x liters iff x is divisible by gcd(a,b), by Bezout's identity), LC 914 (X of a Kind — gcd of all counts).”}},{“@type”:”Question”,”name”:”How does the Sieve of Eratosthenes work and when do you use it?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Initialize is_prime[0..N] = True, set is_prime[0]=is_prime[1]=False. For each i from 2 to sqrt(N): if is_prime[i], mark all multiples of i starting from i*i as False. Time O(N log log N), Space O(N). Start the inner loop at i*i because smaller multiples (2*i, 3*i, …, (i-1)*i) were already marked by smaller primes. Use the sieve when: you need all primes up to N (LC 204 Count Primes), you need to factorize many numbers efficiently (precompute smallest prime factor: spf[i] = smallest prime that divides i, then factorize any number in O(log n) using spf), or you need to check primality for many values.”}},{“@type”:”Question”,”name”:”How does modular arithmetic work in coding problems?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Key rules: (a+b)%m = ((a%m)+(b%m))%m; (a*b)%m = ((a%m)*(b%m))%m. Apply mod at each step to keep numbers small. For division: you cannot simply divide modularly. Instead, use modular inverse: a/b mod m = a * b^(m-2) mod m, valid when m is prime (Fermat's little theorem). In Python: pow(b, m-2, m). Standard modulus in competitive programming: 10^9 + 7 (prime). When a problem says "return the answer mod 10^9+7", apply mod after every addition and multiplication in your DP. Never compute the full value and mod at the end — it will overflow in most languages (Python handles big ints natively but is slow for very large numbers).”}},{“@type”:”Question”,”name”:”How do you compute nCr mod p for combinatorics problems?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Precompute factorial and inverse factorial arrays up to MAX_N. Build: fact[i] = fact[i-1] * i % MOD. Build inv_fact in reverse: inv_fact[MAX-1] = pow(fact[MAX-1], MOD-2, MOD); inv_fact[i] = inv_fact[i+1] * (i+1) % MOD. Then nCr(n,r) = fact[n] * inv_fact[r] % MOD * inv_fact[n-r] % MOD. This gives O(1) per query after O(N) preprocessing. Use for: counting paths in a grid (LC 62), counting valid arrangements, distributing items. Edge cases: nCr = 0 if r < 0 or r > n. For very small n: Pascal's triangle is simpler. For competitive programming: precompute up to 10^5 or 10^6 as needed.”}},{“@type”:”Question”,”name”:”How do you use prime factorization to solve graph problems?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”LC 952 (Largest Component Size by Common Factor): build a graph where numbers sharing a prime factor are connected, find the largest connected component. Key insight: instead of connecting every pair of numbers with a common factor (O(N^2)), factor each number and use Union-Find to connect each number to its prime factors (treating primes as virtual nodes). For each number n: factorize n, union(n, prime_factor) for each prime factor. The component of each number includes all numbers sharing any prime factor. Factorize each number in O(sqrt(n)); total time O(N*sqrt(MAX_VAL)). Prime factorization also appears in: counting divisors (product of (exponent+1) for each prime factor), finding perfect squares, and LCM computations.”}}]}
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.