Number Theory
Use number theory or cross products to preserve a mathematical invariant.
The idea
Euclid's algorithm relies on gcd(a, b) = gcd(b, a mod b), rapidly reducing a pair until the remainder is zero. Computational geometry uses the sign of a 2D cross product to distinguish left, right, and collinear turns along an ordered boundary.
This visualization makes the state transitions behind number theory explicit, one decision at a time.
When to reach for it
- The problem exhibits this pattern's defining invariant.
- A direct brute-force approach repeats work or explores unnecessary choices.
- You need a standard interview-ready template.
Language-independent template
choose the mathematical invariant
update or classify one state at a time
interpret the terminal invariantComplexity — time O(log min(a,b)) for GCD; O(n) for polygon turns, space O(1) algorithmically.
Common mistakes
- Choosing the wrong state or invariant.
- Updating state before preserving the value needed next.
- Missing a boundary or base case.
Practice progression
Canonical interview problems, ordered from foundation to advanced application.
Find the GCD of the smallest and largest array values.
Compute a power efficiently for positive or negative exponents.
Find the largest number of collinear points.