Math & Geometry

Number theory, overflow-safe arithmetic, fast powers, primes, cross products and random sampling: the small set of math tools that turns brute force into O(log n) or O(1).

Overview

Math problems in coding rarely need advanced math. They need a handful of tools you can write from memory: Euclid's algorithm, fast exponentiation, the sieve, modular arithmetic, the cross product and two sampling algorithms. The skill being tested is spotting which tool fits, then writing it without overflow or off-by-one bugs.

Spot the tool

Read the problem for the signal, then reach for the tool. Most brute-force answers are O(n) or worse; the tool usually gives O(log n) or O(1).

fractions, 'divides evenly', a repeating cycle length — GCD and LCM (Euclid) — O(log min(a, b))
x to a large power, 'answer modulo 10^9 + 7' — fast exponentiation, modular arithmetic — O(log n)
'count the primes below n', many primality checks — Sieve of Eratosthenes — O(n log log n)
one primality check — trial division up to the square root — O(sqrt n)
digits of a number, reverse, palindrome — % 10 and // 10 in a loop — O(number of digits)
turn direction, collinear points, segment crossing — cross product — O(1)
boxes or intervals that overlap — max of starts, min of ends — O(1)
random order, random pick from a stream — Fisher-Yates, reservoir sampling — O(n)

Matrix rotation and spiral order look like geometry but are index bookkeeping; they live in the Matrix topic.

Euclid's algorithm for GCD

The greatest common divisor of a and b does not change if you replace a with a mod b, because any number that divides both a and b also divides a - q*b. So repeat (a, b) = (b, a % b) until b is 0; a is the answer.

1 — 48 — 18 — 12
2 — 18 — 12 — 6
3 — 12 — 6 — 0
4 — 6 — 0 — done: gcd = 6

The remainder at least halves every two steps, so the loop runs O(log min(a, b)) times. The least common multiple follows from it: lcm(a, b) = a // gcd(a, b) * b. Divide first so the intermediate value stays small in languages with fixed-width integers. Python has math.gcd (any number of arguments since 3.9) and math.lcm (3.9).

Fast exponentiation

To compute x to the n, write n in binary. Each bit of n says whether a power x^1, x^2, x^4, x^8 and so on belongs in the product. Square the base once per bit and multiply it into the result when the bit is 1. That is about log2(n) squarings instead of n - 1 multiplications.

Trace for 3^13, where 13 is 1101 in binary.

1101 — 1 — 1 * 3 = 3 — 9
110 — 0 — 3 — 81
11 — 1 — 3 * 81 = 243 — 6561
1 — 1 — 243 * 6561 = 1594323 — done

The result is 3^1 * 3^4 * 3^8 = 3^13 = 1594323. With a modulus, reduce after every multiplication so numbers never grow past mod squared. Python's built-in pow(base, exp, mod) does exactly this, and since Python 3.8 a negative exponent with a modulus returns the modular inverse.

Modular arithmetic and overflow

Many problems ask for an answer modulo 10^9 + 7 because the true answer is huge. Addition, subtraction and multiplication can be reduced at every step, because (a * b) % m == ((a % m) * (b % m)) % m. Division cannot: to divide by b, multiply by b's modular inverse, which exists when b and m share no factor. When m is prime, the inverse is b^(m-2) mod m (Fermat's little theorem).

Languages differ, and the difference matters.

integer size — unlimited precision — int is 32-bit, long is 64-bit
on overflow — never overflows — wraps silently to the low-order bits
-7 % 3 — 2 (sign follows the divisor) — -1 (sign follows the dividend)
-7 // 3 or -7 / 3 — -3 (rounds toward minus infinity) — -2 (rounds toward zero)
safe helpers — not needed — Math.multiplyExact throws on overflow; Math.floorMod gives a non-negative mod for a positive divisor

A Java int holds at most 2,147,483,647, so mid * mid already overflows at mid = 46,341. Use long, or compare mid n.

Trace for n = 30.

2 — 4, 6, 8, ..., 30 — all 14
3 — 9, 12, 15, ..., 30 — 9, 15, 21, 27
5 — 25, 30 — 25
7 — nothing: 49 > 30, so stop

Left unmarked: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. The work is O(n log log n) time and O(n) space. For one number, trial division by 2 and odd numbers up to its square root is O(sqrt n) and needs no array.

Geometry with the cross product

For points O, A and B, the cross product (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x) tells you which way you turn going from O to A to B. It uses only integer multiplication, so it has no floating-point error, and it is twice the signed area of triangle OAB.

positive — B is left of OA: counterclockwise turn — B = (2, 3) gives 12
negative — B is right of OA: clockwise turn — B = (2, -3) gives -12
zero — collinear — B = (8, 0) gives 0

Prefer the cross product to slopes: slopes need division, fail on vertical lines and lose precision as floats. When you do need a slope as a key (Max Points on a Line), store the reduced pair (dy / g, dx / g) with g = gcd(dy, dx) and a fixed sign.

Rectangle overlap is two interval overlaps

Two axis-aligned rectangles overlap exactly when their x-ranges overlap and their y-ranges overlap. Two ranges overlap when the later start is before the earlier end.

x — 0 to 4 — 2 to 6 — min(4, 6) - max(0, 2) = 2
y — 0 to 3 — 1 to 5 — min(3, 5) - max(0, 1) = 2

Both lengths are positive, so they overlap with area 2 * 2 = 4. Clamp each length at 0 with max(0, ...); a length of exactly 0 means the rectangles only touch.

Random sampling

Fisher-Yates shuffle walks i from the last index down to 1 and swaps position i with a random j in [0, i]. Every permutation comes out with probability 1/n!. Picking j from the whole array at every step looks similar but is biased: it has n^n equally likely paths, which cannot split evenly over n! orders.

Reservoir sampling picks k items uniformly from a stream whose length you do not know. Keep the first k. For the item at 0-based index i (i >= k), pick j in [0, i]; if j < k, replace slot j. Trace for k = 1 over a stream of 3 items.

0 — 1 — 1/2 * 2/3 — 1/3
1 — 1/2 — 2/3 — 1/3
2 — 1/3 — 1 — 1/3

What you will be able to do

Match a problem statement to the right tool from the signal table.
Write Euclid's GCD, fast power with a modulus and the sieve from memory, with their costs.
Explain overflow and negative modulo in Python and Java, and how to avoid both.
Use the cross product for turns, collinearity and segment crossing without floating point.
Write an unbiased shuffle and reservoir sampling, and say why they are uniform.

When to use it

Digit problems: reverse a number, palindrome number, sum of digits.
Large powers or answers modulo 10^9 + 7.
Fractions, divisibility and cycle lengths (GCD and LCM).
Generating primes up to n, or testing one number for primality.
Orientation, collinear points, segment crossing and polygon area (cross product).
Overlap and area of axis-aligned rectangles.
Uniform random order or random picks from a stream.

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio