Math Problems in Coding Interviews — GCD, Primes, and Modular Arithmetic

Math-heavy interview questions feel like they require a number theory background. They don't. There's a short list of concepts that covers 95% of what you'll encounter: GCD, primes, modular arithmetic, and a handful of combinatorial formulas. The hard part isn't the math — it's recognizing that a problem is a math problem disguised as something else.

GCD and LCM

The greatest common divisor comes up constantly. Use the Euclidean algorithm — it's been around for 2300 years because it works.

Euclidean Algorithm

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

function gcd(a, b) {
  while (b) {
    [a, b] = [b, a % b];
  }
  return a;
}

function lcm(a, b) {
  return (a * b) / gcd(a, b);
}

Python has math.gcd built in. JavaScript doesn't (yet), so know how to write it.

Time complexity: O(log(min(a,b))). Each step reduces the larger number by at least half. This is surprisingly fast — GCD of two 64-bit numbers takes at most ~90 iterations.

Extended Euclidean Algorithm

Finds x and y such that ax + by = gcd(a, b). You need this for modular inverses.

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = extended_gcd(b, a % b)
    return g, y, x - (a // b) * y

function extendedGcd(a, b) {
  if (b === 0) return [a, 1, 0];
  const [g, x, y] = extendedGcd(b, a % b);
  return [g, y, x - Math.floor(a / b) * y];
}

When You Need GCD

• "Reduce a fraction to lowest terms" — divide numerator and denominator by their GCD
• "Water jug problem" — you can measure exactly the volumes that are multiples of GCD(jug1, jug2)
• LCM calculations (scheduling problems, "when do two cycles align?")
• Array problems: "GCD of all elements," "pairs with GCD = 1"

Prime Numbers

Sieve of Eratosthenes

Generate all primes up to n in O(n log log n). This is the right approach whenever you need many primes or need to check primality for numbers in a range.

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(n + 1) if is_prime[i]]

function sieve(n) {
  const isPrime = new Array(n + 1).fill(true);
  isPrime[0] = isPrime[1] = false;

for (let i = 2; i * i <= n; i++) {
    if (isPrime[i]) {
      for (let j = i * i; j <= n; j += i) {
        isPrime[j] = false;
      }
    }
  }

return isPrime.reduce((primes, val, idx) => {
    if (val) primes.push(idx);
    return primes;
  }, []);
}

Starting the inner loop at i i (not 2 i) is an optimization — smaller multiples have already been marked by smaller primes.

Primality Test for a Single Number

Don't sieve for one number. Trial division up to sqrt is fine.

def is_prime(n):
    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

function isPrime(n) {
  if (n < 2) return false;
  if (n < 4) return true;
  if (n % 2 === 0 || n % 3 === 0) return false;
  for (let i = 5; i * i <= n; i += 6) {
    if (n % i === 0 || n % (i + 2) === 0) return false;
  }
  return true;
}

The i += 6 trick: after eliminating multiples of 2 and 3, all remaining primes are of the form 6k ± 1. So you check i and i+2, then jump by 6.

Prime Factorization

def prime_factors(n):
    factors = {}
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors[d] = factors.get(d, 0) + 1
            n //= d
        d += 1
    if n > 1:
        factors[n] = factors.get(n, 0) + 1
    return factors

function primeFactors(n) {
  const factors = new Map();
  for (let d = 2; d * d <= n; d++) {
    while (n % d === 0) {
      factors.set(d, (factors.get(d) || 0) + 1);
      n = Math.floor(n / d);
    }
  }
  if (n > 1) factors.set(n, (factors.get(n) || 0) + 1);
  return factors;
}

O(sqrt(n)) for a single number. For multiple numbers, sieve first and use the smallest prime factor (SPF) table for O(log n) factorization.

Modular Arithmetic

When problems say "return the answer modulo 10^9 + 7," they're telling you the answer is astronomically large. You need modular arithmetic to keep numbers manageable.

The Rules

(a + b) mod m = ((a mod m) + (b mod m)) mod m
(a  b) mod m = ((a mod m)  (b mod m)) mod m
(a - b) mod m = ((a mod m) - (b mod m) + m) mod m  // +m to avoid negatives

Division is NOT modular. You need modular inverse (below).

Modular Exponentiation (Fast Power)

Compute a^b mod m in O(log b) using repeated squaring.

def mod_pow(base, exp, mod):
    result = 1
    base %= mod
    while exp > 0:
        if exp % 2 == 1:
            result = result * base % mod
        exp //= 2
        base = base * base % mod
    return result

function modPow(base, exp, mod) {
  let result = 1n;
  base = BigInt(base) % BigInt(mod);
  exp = BigInt(exp);
  mod = BigInt(mod);

while (exp > 0n) {
    if (exp % 2n === 1n) {
      result = (result * base) % mod;
    }
    exp /= 2n;
    base = (base * base) % mod;
  }

return Number(result);
}

Python handles big integers natively. JavaScript needs BigInt for large modular exponentiation to avoid precision loss.

Python shortcut: pow(base, exp, mod) — the built-in three-argument pow does modular exponentiation.

Modular Inverse

To divide by a modulo m, multiply by a's modular inverse: a^(-1) mod m.

When m is prime (like 10^9 + 7), use Fermat's little theorem: a^(-1) ≡ a^(m-2) mod m.

def mod_inverse(a, m):
    return pow(a, m - 2, m)

function modInverse(a, m) {
  return modPow(a, m - 2, m);
}

When m isn't prime, use the extended Euclidean algorithm. The inverse exists only when gcd(a, m) = 1.

nCr Modulo a Prime

Combination count (n choose r) with modular arithmetic. Precompute factorials and inverse factorials.

MOD = 10**9 + 7

def precompute(n):
    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] = 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, r, fact, inv_fact):
    if r < 0 or r > n:
        return 0
    return fact[n]  inv_fact[r] % MOD  inv_fact[n - r] % MOD

Precompute once, then each nCr query is O(1).

Powers of Two and Bit Counting

Not strictly number theory, but these patterns show up in "math" interview questions.

# is n a power of 2?
def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0

# count set bits
def count_bits(n):
    count = 0
    while n:
        count += 1
        n &= n - 1  # clears lowest set bit
    return count

function isPowerOfTwo(n) {
  return n > 0 && (n & (n - 1)) === 0;
}

function countBits(n) {
  let count = 0;
  while (n) {
    count++;
    n &= n - 1;
  }
  return count;
}

Complexity Summary

Operation	Time	Notes
GCD (Euclidean)	O(log min(a,b))
Sieve of Eratosthenes	O(n log log n)	Up to n
Primality test	O(sqrt(n))	Single number
Prime factorization	O(sqrt(n))	Single number
Modular exponentiation	O(log exp)
nCr with precomputation	O(n) precompute, O(1) query

Problem Shapes That Signal Math

• "Return answer modulo 10^9 + 7" → modular arithmetic, likely combinatorics
• "Reduce fraction" → GCD
• "Count of numbers in range with property X" → sieve or digit DP
• "When do two events coincide?" → LCM
• "Distribute items into groups" → combinatorics (nCr)
• "Can you measure exactly X?" → GCD (Bézout's identity)

Common Mistakes

Integer overflow. In JavaScript, numbers lose precision above 2^53. Use BigInt for modular arithmetic with large numbers. Python handles this automatically. Forgetting the +m in modular subtraction. (a - b) % m can be negative in most languages. Add m before taking mod. Using floating-point division for mod operations. Division isn't distributive over mod. Use modular inverse, not actual division. Sieving too large a range. Sieve of Eratosthenes needs O(n) memory. For n = 10^12, that's not going to work. Use segmented sieve or Miller-Rabin for large numbers. Not reading "modulo 10^9 + 7" in the problem statement. If your answer overflows without modular arithmetic, reread the problem. It's probably there.

Practice math problems on CodeUp — they test a different muscle than typical array/tree problems, and skipping them leaves a gap in your preparation.