GCD, LCM, and Euclidean Algorithm
import math
def gcd(a: int, b: int) -> int:
while b:
a, b = b, a % b
return a # O(log(min(a,b))) by Euclidean algorithm
def lcm(a: int, b: int) -> int:
return a * b // gcd(a, b)
# GCD applications:
# Simplify fraction: gcd(numerator, denominator)
# Check if two numbers are coprime: gcd(a, b) == 1
# Find all divisors: for i in range(1, int(n**0.5)+1): if n%i==0: divisors += [i, n//i]Sieve of Eratosthenes — All Primes up to n
def sieve(n: int) -> list[int]:
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]]
# O(n log log n) time, O(n) space
# Use for: count primes (LC 204), prime factorization of many numbers
def is_prime(n: int) -> bool:
if n < 2: return False
if n < 4: return True
if n % 2 == 0 or n % 3 == 0: return False
i = 5
while i * i <= n:
if n % i == 0 or n % (i+2) == 0: return False
i += 6
return True # O(sqrt(n))Modular Arithmetic
# All results mod M = 10^9 + 7 (prime, standard in competitive programming)
MOD = 10**9 + 7
# (a + b) % M = (a % M + b % M) % M
# (a * b) % M = (a % M * b % M) % M
# (a - b) % M = (a % M - b % M + M) % M -- add M to avoid negative
# Division: (a / b) % M = (a * modular_inverse(b, M)) % M
def mod_pow(base: int, exp: int, mod: int) -> int:
result = 1
base %= mod
while exp > 0:
if exp % 2 == 1:
result = result * base % mod
base = base * base % mod
exp //= 2
return result
def mod_inverse(a: int, mod: int) -> int:
# Fermat's little theorem: a^(mod-1) = 1 (mod) when mod is prime
return mod_pow(a, mod - 2, mod)Combinatorics: nCr and Pascal’s Triangle
# Precompute factorials for fast nCr queries
def precompute_factorials(n: int, mod: int) -> tuple:
fact = [1] * (n + 1)
for i in range(1, n + 1):
fact[i] = fact[i-1] * i % mod
inv_fact = [1] * (n + 1)
inv_fact[n] = mod_pow(fact[n], mod - 2, mod)
for i in range(n-1, -1, -1):
inv_fact[i] = inv_fact[i+1] * (i+1) % mod
return fact, inv_fact
def ncr(n: int, r: int, fact: list, inv_fact: list, mod: int) -> int:
if r n: return 0
return fact[n] * inv_fact[r] % mod * inv_fact[n-r] % mod
# Catalan number: C(n) = C(2n, n) / (n+1)
# Used for: number of valid parenthesis sequences, BST structures with n nodes,
# number of monotone paths, triangulations of polygons
def catalan(n: int) -> int:
return ncr(2*n, n, *precompute_factorials(2*n, MOD), MOD) * mod_inverse(n+1, MOD) % MODCommon Math Patterns
# Happy Number (LC 202): detect cycle with fast/slow pointers on digit sum
def is_happy(n: int) -> bool:
def digit_square_sum(x):
return sum(int(d)**2 for d in str(x))
slow, fast = n, digit_square_sum(n)
while fast != 1 and slow != fast:
slow = digit_square_sum(slow)
fast = digit_square_sum(digit_square_sum(fast))
return fast == 1
# Reverse integer (LC 7): handle overflow
def reverse(x: int) -> int:
sign = -1 if x < 0 else 1
rev = int(str(abs(x))[::-1])
result = sign * rev
return result if -(2**31) <= result int:
n = len(nums)
return n * (n + 1) // 2 - sum(nums)
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What is the time complexity of the Euclidean GCD algorithm?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”The Euclidean algorithm runs in O(log(min(a,b))) time. Each step reduces the larger number by at least half, leading to logarithmic convergence. It is the standard approach for GCD in interviews and competitive programming.”}},{“@type”:”Question”,”name”:”How does the Sieve of Eratosthenes work and what is its complexity?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”The sieve initializes a boolean array of size n+1, then for each prime p starting from 2, marks all multiples of p as composite. It runs in O(n log log n) time and O(n) space. Use it when you need all primes up to n, such as in LC 204 (Count Primes).”}},{“@type”:”Question”,”name”:”Why is MOD = 10^9 + 7 used in competitive programming?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”10^9 + 7 is a large prime number. Using a prime modulus enables modular inverse via Fermat's little theorem: a^(MOD-2) mod MOD. It is large enough to prevent overflow in intermediate calculations when using 64-bit integers, and is the standard modulus in competitive programming and interview problems.”}},{“@type”:”Question”,”name”:”How do you compute nCr efficiently for large n with modular arithmetic?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Precompute factorial and inverse factorial arrays up to n. Then nCr = fact[n] * inv_fact[r] * inv_fact[n-r] mod MOD. Each query is O(1) after O(n) precomputation. The inverse factorial array is built by computing inv_fact[n] = mod_pow(fact[n], MOD-2, MOD), then iterating down: inv_fact[i] = inv_fact[i+1] * (i+1) mod MOD.”}},{“@type”:”Question”,”name”:”What are Catalan numbers used for in coding interviews?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Catalan numbers count many combinatorial structures: number of valid parenthesis sequences of length 2n (LC 22), number of structurally unique BSTs with n nodes (LC 96), number of ways to triangulate a convex polygon, and number of monotone paths through an n x n grid that do not cross the diagonal. C(n) = C(2n,n) / (n+1).”}}]}
Meta coding interviews frequently test modular arithmetic, GCD, and prime factorization. See common patterns in Meta interview questions on number theory and modular arithmetic.
Atlassian interviews include combinatorics and number theory questions. Review typical problem patterns in Atlassian interview: math and combinatorics problems.
Coinbase interviews test modular arithmetic and number theory relevant to cryptographic foundations. See Coinbase interview: cryptography and number theory foundations.