Math and Geometry: The Core Idea

Raise 1.0000001 to the power of one billion. The obvious loop multiplies a billion times. Measured in Python, ten million multiplications took 0.2 seconds, so a billion takes about 20 seconds — and the time limit is one second. A different loop, which reads the exponent in binary, got the same answer in 8 microseconds with 43 multiplications.

That is typical of this section. The problems do not need a clever data structure. They need one fact — that exponents split into powers of two, that the GCD of two numbers equals the GCD of the smaller one and the remainder, that three points are on a line when a certain product is zero. If you know the fact, the code is ten lines. If you do not, you spend the interview rediscovering it.

The good news is that the list of facts is short. Unlike dynamic programming, there is no skill to build over weeks. This lesson is the list, and the problem lessons after it apply each fact to the question interviewers actually ask.

A different kind of pattern

Most sections in this course teach one mechanism — two pointers, a sliding window, a heap. This one teaches a toolbox. The problems fall into four groups, and naming the group is the first step:

• Matrix manipulation. A 2-D grid and a spatial operation: rotate, spiral, transpose, mark rows and columns. The difficulty is index arithmetic.
• Number theory. Divisors, primes, remainders, GCD, or an answer "modulo 10⁹ + 7".
• Fast arithmetic. Powers, roots or repeated multiplication with a huge exponent.
• Coordinate geometry. Points, lines, distances, areas, overlaps.

How to recognise it

Signals in the statement:

• "Return the answer modulo 10⁹ + 7." The true answer is enormous. You must take the remainder at every step.
• An exponent or count up to 10⁹, with no array to go with it. An O(n) loop is impossible. The answer is O(log n) — fast exponentiation, or binary search on the answer — or a closed formula.
• "In place" on a matrix, or "O(1) extra space". The trick is usually an index identity, or storing markers inside the matrix itself.
• "All primes below n", "count divisors", "greatest common divisor". Number theory, usually the sieve or Euclid.
• Points with integer coordinates. Geometry — and a warning to stay in integers.

The constraints give the same hints. "n ≤ 5 × 10⁶" with a question about primes means an O(n log log n) sieve. "−2³¹ ≤ n ≤ 2³¹ − 1" as an exponent means O(log n). "n ≤ 300 points" means O(n²) pairs is the target and O(n³) triples is borderline.

How it works: the core facts

Euclid's algorithm for the GCD

The greatest common divisor (GCD) of two numbers is the largest integer that divides both. Trying every candidate from min(a, b) downward costs O(min(a, b)) — a billion checks for a = 10⁹.

Euclid's fact: any number that divides both a and b also divides a mod b, because a mod b = a − k × b for some whole k. So the pair (a, b) and the pair (b, a mod b) have exactly the same common divisors — and the second pair is smaller. Repeat until the remainder is 0. The last non-zero number is the GCD.

1def gcd(a: int, b: int) -> int:2    """Greatest common divisor by Euclid's algorithm."""3    while b:4        a, b = b, a % b     # same common divisors, smaller pair5    return a678def lcm(a: int, b: int) -> int:9    """Least common multiple; divide first so the product stays small."""10    return a // gcd(a, b) * b

Trace gcd(48, 18):

Why O(log n)? After two steps, the first number has at least halved. (If b ≤ a/2, the remainder is below b ≤ a/2; if b > a/2, the remainder is a − b, below a/2.) Halving every two steps means O(log(min(a, b))) steps. Python ships this as math.gcd, which also handles negatives and zero: math.gcd(0, 5) is 5.

The least common multiple is a × b / gcd(a, b): lcm(48, 18) = 48 / 6 × 18 = 144. Dividing first keeps the intermediate small, which matters in Java or C++.

Modular arithmetic

When a problem says "return the answer modulo 10⁹ + 7", take the remainder after every operation, not once at the end. Three rules make that legal:

1MOD = 10**9 + 72a, b = 10**18 + 3, 987_654_321_987            # any integers work34assert (a + b) % MOD == ((a % MOD) + (b % MOD)) % MOD5assert (a - b) % MOD == ((a % MOD) - (b % MOD)) % MOD   # Python's % is never negative here6assert (a * b) % MOD == ((a % MOD) * (b % MOD)) % MOD

Division does not follow this rule. To divide by b under a prime modulus, multiply by b's modular inverse, which is pow(b, MOD - 2, MOD) by Fermat's little theorem. For b = 2 that is 500000004, and 2 × 500000004 % MOD is 1, as an inverse should be.

Why 10⁹ + 7? It is prime, so every non-zero value has an inverse. And it is small enough that the product of two values below it, about 10¹⁸, fits in a signed 64-bit integer (up to about 9.2 × 10¹⁸).

In Python, reducing once at the end still gives the right answer — Python integers never overflow — but the intermediate number can grow to millions of digits and become very slow. In Java or C++, reducing every step is required for correctness.

Primes

Testing each number up to n by trial division costs O(n√n). The sieve of Eratosthenes crosses off multiples of each prime instead and costs O(n log log n). The Count Primes lesson builds it step by step.

Geometry in integers

Three habits keep geometry exact:

• Compare squared distances. d1 < d2 exactly when d1² < d2², so skip the square root when you only compare.
• Test turn direction and collinearity with the cross product. For points o, a, b:

def cross(o: tuple[int, int], a: tuple[int, int], b: tuple[int, int]) -> int:    """Twice the signed area of triangle o-a-b: >0 left turn, <0 right turn, 0 collinear."""    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

For (0, 0), (1, 1), (2, 2) it is 0 — one line. For (0, 0), (1, 1), (3, 1) it is −2 — a right turn. No division, so no divide-by-zero on vertical lines and no rounding.

• Store a slope as a reduced fraction, (dx / g, dy / g) with g = gcd, never as a float. Max Points on a Line shows why.

Variants: the forms it takes

The template: work a small example first

There is no single code template here. There is a single habit, and it prevents more bugs than any template:

1. Draw the smallest real example — a 3 × 3 matrix, gcd(48, 18), three points — and work it by hand.
2. Write the index formula from the example, and check it on one corner and one middle cell.
3. Pick an asymmetric test — a 2 × 4 matrix, a negative coordinate, a vertical line — because symmetric inputs hide swapped rows and columns.
4. Code it, then run the hand example through the code and compare line by line.

Index bugs that survive a mental review do not survive a worked 3 × 3 grid.

Complexity

Measured in Python: counting primes below 5 × 10⁶ took 20.8 seconds by trial division and under half a second with the sieve.

Where it goes wrong

1. Integer overflow. Not a Python problem, but a real one everywhere else, and interviewers like to hear you raise it. a * b before dividing by the GCD, n * (n + 1) in a sum formula, and squared distances all pass 2³¹ quickly: coordinates of 10⁵ give squares of 10¹⁰. The fixes: a 64-bit type, dividing before multiplying, or reducing modulo at every step. Saying "in Java this needs a long" while writing Python shows production experience.

2. Floating-point equality. 0.1 + 0.2 == 0.3 is False, because 0.1 has no exact binary form. Any geometry that compares computed floats for equality is fragile. In order of preference: stay in integers; compare with a tolerance like abs(a - b) < 1e-9; or use exact types such as fractions.Fraction. Never put a tolerance inside a sort key — "almost equal" is not transitive.

3. Negative modulo differs by language. In Python, -7 % 3 is 2 and 7 % -3 is -2: the result takes the sign of the divisor. In Java, C, C++ and JavaScript, -7 % 3 is -1 and 7 % -3 is 1: the sign of the dividend. A circular index (i - 1) % n is safe in Python at i = 0 and crashes in Java. The portable form is ((a % n) + n) % n.

4. Matrix boundaries. Three forms. Transposing the whole square instead of the upper triangle swaps each pair twice and changes nothing. A spiral without guards emits a single row twice. And for a non-square grid, len(matrix) is the row count and len(matrix[0]) the column count; swapping them passes on square tests and crashes on rectangles.