Math tricks worth memorizing
📖 Walk me through it — plain English
This lesson is a small toolbox of math patterns that show up over and over in interviews. The big four are: modular arithmetic (doing math but only ever keeping the remainder after dividing by some number), fast exponentiation (raising a number to a big power quickly), GCD/LCM (greatest common divisor and least common multiple of two numbers), and the Sieve of Eratosthenes (a fast way to list every prime number up to some limit). You care because each one turns a problem that looks scary into a handful of lines you can write from memory.
Quick jargon, plainly. "Modulo" (the % sign) just means "the remainder after dividing" — 17 % 5 is 2, because 17 is three fives (15) with 2 left over. A "prime" is a whole number bigger than 1 whose only divisors are 1 and itself (2, 3, 5, 7, 11…). The remainder rules at the top let you take % at every step instead of only at the end, which keeps numbers small so they never overflow (grow past what the computer can store).
An everyday analogy for the Sieve: imagine a long list of house numbers and you want only the "prime" houses. You walk to the first un-crossed house (2), then cross out every house that is a multiple of it — every 2nd, 4th, 6th… because those can be divided by 2, so they aren't prime. Then you walk to the next house still standing (3) and cross out its multiples. Whatever houses survive the whole walk are the primes. The clever bit: when you're at house i, you can start crossing from i × i, because every smaller multiple of i was already crossed by an earlier, smaller number.
Here is the Sieve traced for N = 10. We keep a row of "is this prime?" flags for the numbers 0 through 10. Boxes that are crossed out (struck through, faded) are NOT prime; the box in accent color is the number i we are currently standing on; survivors at the end turn green.
Why the Sieve is so fast (O(N log log N), basically linear for our purposes): each composite number gets crossed off only a few times — once per distinct prime that divides it — instead of being individually tested for primality. The same "do the cheap thing repeatedly" spirit powers the other tools here. Fast exponentiation squares the base and halves the exponent each loop (exp >>= 1 shifts the bits right, i.e. divides by 2), so a power of n only takes about log₂(n) steps instead of n multiplications. Euclid's GCD keeps replacing the pair with (smaller, remainder) via a, b = b, a % b — the numbers shrink fast, so it also finishes in about log steps. The unifying idea: when you can halve or remainder your way down, an enormous input collapses to a tiny number of steps.
Modular arithmetic, fast exponentiation, GCD/LCM, the Sieve. A handful of patterns covers most "math" interview questions.
(a + b) % m = ((a % m) + (b % m)) % m(a · b) % m = ((a % m) · (b % m)) % m- No "mod division" — use modular inverse via Fermat's little theorem when m is prime:
a⁻¹ ≡ a^(m-2) mod m - Why interview problems mod 10⁹+7: keeps results in 64-bit range and avoids overflow during multiplication.
def pow_mod(base, exp, mod):
result = 1
base %= mod
while exp:
if exp & 1:
result = (result * base) % mod
base = (base * base) % mod
exp >>= 1
return resultdef gcd(a, b):
while b:
a, b = b, a % b
return a
def lcm(a, b):
return a * b // gcd(a, b)Euclid's algorithm: O(log min(a, b)). Why divide for LCM first? To avoid overflow on a*b.
def sieve(n):
is_p = [True] * (n + 1)
is_p[0] = is_p[1] = False
for i in range(2, int(n**0.5) + 1):
if is_p[i]:
for j in range(i*i, n + 1, i):
is_p[j] = False
return [i for i, p in enumerate(is_p) if p]O(N log log N) — effectively linear. Start crossing at i² because smaller multiples are already crossed.
Modular exponentiation — square-and-multiply in O(log exp):