Math for Interviews

Intermediate · 22 min read · Problem-Solving Patterns, Design, Matrices & Advanced Topics

GCD, primes and the sieve, fast power, modular arithmetic, overflow, and random sampling.

Many people skip maths because it feels like a separate subject they "were never good at". But interview maths is a short, fixed list: gcd, primes, fast power, modular arithmetic, overflow, digits and random sampling. Each one is a tiny template you can learn in an afternoon.

GCD and LCM: Euclid's algorithm

gcd(a, b) = gcd(b, a mod b), because any divisor of a and b also divides a mod b. The numbers shrink at least as fast as Fibonacci numbers, so it's O(log min(a, b)):

Primes

One number: trial division up to √n. If n has a factor bigger than √n, it also has one smaller than √n.

Fast power: exponentiation by squaring

To compute x^n for n up to 10¹⁸, use the binary digits of n:

Modular arithmetic: "return it mod 10⁹ + 7"

Answers that grow exponentially (counting paths, arrangements) are reported modulo the prime MOD = 1_000_000_007. The rules:

Overflow and digits

Check before you multiply. To reverse an integer's digits safely, compare with Integer.MAX_VALUE / 10 before computing r * 10 + d:

Randomness

Shuffle (Fisher–Yates). For i from the end down to 1, swap a[i] with a random index in 0..i. Each of the n! orders is equally likely. Picking from 0..n−1 at every step instead is a famous bug: it produces nⁿ equally likely outcomes, which can't divide evenly into n! orders.

Practice ladder

Interview questions

  • Why does exponentiation by squaring need only O(log n) multiplications?
  • How do you divide when the answer must be returned modulo 10⁹ + 7?

Further reading

Key takeaways

  • GCD by Euclid in O(log n); LCM = a / gcd · b to avoid overflow.
  • Primes: trial division to √n; the sieve for all primes up to n in O(n log log n).
  • Fast power squares the base and multiplies on 1-bits: O(log n).
  • Mod after every operation; divide by multiplying with the Fermat inverse; precompute factorials for nCr.
  • Check overflow before multiplying; Fisher–Yates for shuffles; reservoir sampling for streams.

Previous: Matrix & Simulation · Next: String Matching: KMP & Rolling Hash