Math and Number Theory Interview Patterns: GCD, Primes, Modular Arithmetic, and Combinatorics (2025)

By /
⏱ 4 min read

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) % MOD

Common 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)

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.

Scroll to Top