Number Theory Interview Patterns

Updated April 17, 2026 · techinterview.org

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.