Math & Geometry

What it is

A grab-bag of problems where the efficient solution comes from a mathematical property of the input, not from a reusable algorithmic template like DP or two pointers.

Recurring building blocks

• Prime factorization / sieve of Eratosthenes — precompute primality for a range in O(n log log n), reused across many number-theory problems.
• GCD/LCM via the Euclidean algorithm — O(log(min(a,b))), the basis for simplifying fractions and cycle-length problems.
• Modular arithmetic — (a * b) % m avoids overflow on large products; needed whenever a problem asks for "the answer mod 10^9 + 7."
• Coordinate geometry — rotating a matrix in place, checking if points are collinear (cross product), computing area (shoelace formula).

The tell

These problems often don't map cleanly onto arrays/graphs/DP — the fastest way to recognize one is that a small worked example reveals a formula or invariant (e.g. "rotating 90° swaps (r, c) to (c, n-1-r)") rather than a search or scan.

Prerequisite

Only comfort with arrays and basic arithmetic is assumed — this topic is intentionally independent of the rest of the DSA tree so it can be picked up any time.