Math & Geometry

How it works

Math problems reward spotting a structure that makes simulation unnecessary. Instead of repeating an operation a billion times, find the invariant, the cycle, or the closed formula. Exponentiation by squaring, modular arithmetic and digit manipulation are the everyday tools.

Fast power works because x^n splits into (x^(n/2))², so the number of multiplications follows the bits of n: about log n of them. The same doubling trick applies to matrix powers and to repeated application of any associative operation.

Geometry in interviews usually means grids and coordinates: rotating a matrix, counting points on a line, detecting squares. Prefer integer arithmetic. To compare slopes, store the reduced pair (dy, dx) divided by their greatest common divisor rather than a floating-point ratio.

Watch for overflow and sign. Reversing digits, multiplying large strings, or computing averages can exceed 32-bit limits, and the remainder of a negative number differs between languages. Many problems state 'return the answer modulo 10^9 + 7' precisely so you reduce after every operation.

How to attack it

1. 1Look for a formula, invariant or cycle before simulating.
2. 2Use integer arithmetic; avoid floats for equality checks.
3. 3Reduce modulo M after every addition and multiplication if the answer is modular.
4. 4Check negative inputs, zero, and the largest allowed values for overflow.
5. 5For digit problems, peel digits with % 10 and // 10 instead of converting to strings when overflow matters.

Template

A skeleton to adapt, not a solution to paste. Write it from memory a few times.

def fast_pow(base, exp, mod=None):
    # Exponentiation by squaring: O(log exp) multiplications.
    result = 1
    while exp > 0:
        if exp & 1:                    # this bit of exp is set
            result = result * base if mod is None else result * base % mod
        base = base * base if mod is None else base * base % mod
        exp >>= 1
    return result


def gcd(a, b):
    while b:
        a, b = b, a % b
    return abs(a)


def slope_key(p, q):
    # A hashable, exact slope between two points: reduced (dy, dx) with dx >= 0.
    dy, dx = q[1] - p[1], q[0] - p[0]
    g = gcd(dy, dx) or 1
    dy, dx = dy // g, dx // g
    if dx < 0 or (dx == 0 and dy < 0):
        dy, dx = -dy, -dx
    return (dy, dx)


def digit_sum(n):
    total = 0
    n = abs(n)
    while n:
        total += n % 10
        n //= 10
    return total

What it costs