Math and Geometry Problems

Math problems in interviews are rarely about mathematics. They are about avoiding the numeric traps, and there are three that recur constantly:

Carry propagation. Digit-by-digit arithmetic where the answer can be longer than the input.
Exponentiation. Multiplying nn times is $O(n)$ ; squaring is $O(\log n)$ — and negative exponents plus one asymmetric edge case are where submissions fail.
Floating point. Slopes, averages and divisions computed as floats give wrong answers, not just imprecise ones. The fix is almost always to compare with integer arithmetic instead.

That third point is the theme worth carrying away: when a problem seems to need division, look for a way to compare without dividing.

What you’ll learn

The carry loop, and why the “all nines” case needs a prepend.
Exponentiation by squaring, driven by the bits of the exponent.
Why slopes must be normalised integer pairs, never floats — with the concrete failure.
gcdgcd as a canonicalisation tool, and the sign convention that makes it work.
Three real LeetCode problems solved in the browser: 66, 50, 149.

The cue

Trap 1 — carry propagation

plus_one.py

def plus_one(digits):
    for i in range(len(digits) - 1, -1, -1):     # right to left
        if digits[i] < 9:
            digits[i] += 1
            return digits                        # no carry: done
        digits[i] = 0                            # carry into the next place
    return [1] + digits                          # all nines: 999 -> 1000

plus_one.py

def plus_one(digits):
    for i in range(len(digits) - 1, -1, -1):     # right to left
        if digits[i] < 9:
            digits[i] += 1
            return digits                        # no carry: done
        digits[i] = 0                            # carry into the next place
    return [1] + digits                          # all nines: 999 -> 1000

The early returnreturn is the whole structure: the moment a digit is below 9 there is nothing left to carry, so you stop. Only if the loop completes — meaning every digit was a 9 — do you need a new leading digit.

Trap 2 — exponentiation by squaring

Computing x^nx^n by multiplying nn times is $O(n)$ , which is $2^{31}$ operations at LC 50’s limits. Squaring reduces it to $O(\log n)$ by using the binary representation of the exponent:

$x^{13} = x^{8+4+1} = x^8 \cdot x^4 \cdot x^1$

fast_power.py

def my_pow(x, n):
    if n < 0:
        x, n = 1 / x, -n            # x^-n == (1/x)^n
    result = 1.0
    while n:
        if n & 1:                   # this bit of the exponent is set
            result *= x
        x *= x                      # x, x^2, x^4, x^8, ...
        n >>= 1
    return result

fast_power.py

def my_pow(x, n):
    if n < 0:
        x, n = 1 / x, -n            # x^-n == (1/x)^n
    result = 1.0
    while n:
        if n & 1:                   # this bit of the exponent is set
            result *= x
        x *= x                      # x, x^2, x^4, x^8, ...
        n >>= 1
    return result

Each loop iteration squares xx to represent the next power of two, and multiplies it into the result only when that bit is set. $O(\log n)$ multiplications.

Trap 3 — never compare slopes as floats

Three points are collinear when the slopes between them are equal. The obvious implementation divides:

python

slope = (y2 - y1) / (x2 - x1)      # WRONG

python

slope = (y2 - y1) / (x2 - x1)      # WRONG

This fails in two distinct ways:

Vertical lines divide by zero.
Floating point makes distinct slopes compare equal, or equal slopes compare unequal. With coordinates up to $10^4$ , ratios like 1/31/3 are inexact, and accumulated error makes two genuinely different lines look identical.

The fix is to keep the slope as a normalised integer pair:

normalise_slope.py

from math import gcd
 
 
def slope_key(x1, y1, x2, y2):
    dx, dy = x2 - x1, y2 - y1
    g = gcd(dx, dy)                     # gcd(0, k) == abs(k), so this is safe
    dx, dy = dx // g, dy // g
    if dx < 0 or (dx == 0 and dy < 0):  # canonical direction
        dx, dy = -dx, -dy
    return (dx, dy)

normalise_slope.py

from math import gcd
 
 
def slope_key(x1, y1, x2, y2):
    dx, dy = x2 - x1, y2 - y1
    g = gcd(dx, dy)                     # gcd(0, k) == abs(k), so this is safe
    dx, dy = dx // g, dy // g
    if dx < 0 or (dx == 0 and dy < 0):  # canonical direction
        dx, dy = -dx, -dy
    return (dx, dy)

Canonicalise the sign. Without it, (1, 2)(1, 2) and (-1, -2)(-1, -2) are the same direction but different dictionary keys, so collinear points get split across two buckets and the count comes out too low. Forcing dx > 0dx > 0, and dy > 0dy > 0 when dx == 0dx == 0, gives each direction exactly one representative.

gcd(0, k)gcd(0, k) is abs(k)abs(k), which is what makes vertical (dx == 0dx == 0) and horizontal (dy == 0dy == 0) lines work with no special case — they normalise to (0, 1)(0, 1) and (1, 0)(1, 0).

The one input that would break it is dx == dy == 0dx == dy == 0, since gcd(0, 0) == 0gcd(0, 0) == 0 and the division raises. That happens only for two identical points, and LC 149 guarantees all points are distinct — worth stating, because if duplicates were allowed you would need to count them separately.

Problem	Naive	Better
Plus One	—	$O(n)$ , one pass
`pow(x, n)pow(x, n)`	$O(n)$ multiplications	$O(\log n)$ by squaring
Max points on a line	$O(n^3)$ triples	$O(n^2)$ slope buckets per anchor

The variant map

Variant	The technique	Canonical problem
Increment a digit array	Carry loop + prepend on all-nines	66
Add / multiply as strings	Same carry logic, positional accumulation	415 · 43 · 2
Fast power	Square, driven by exponent bits	50 · 372
Integer square root	Binary search on the answer	69
Collinear points	Normalised integer slope pairs	149
Trailing zeros of `n!n!`	Count factors of 5	172
Count primes	Sieve of Eratosthenes	204
Convex hull / area	Cross products, never slopes	587 · 963

Factorial Trailing Zeroes asks how many zeros end n!n!. Computing n!n! is impossible for large nn — and unnecessary.

A trailing zero comes from a factor of 10, i.e. a pair of 2 and 5. Factors of 2 are far more plentiful than factors of 5, so the answer is just the number of factors of 5 in n!n!:

python

count = 0
while n:
    n //= 5
    count += n
return count

python

count = 0
while n:
    n //= 5
    count += n
return count

Each division counts the multiples of 5, then of 25, then of 125, and so on — since 25 contributes two 5s, 125 contributes three. $O(\log_5 n)$ , no factorial computed.

This is the archetype of a math problem where the insight is the whole solution and the code is four lines. When a problem seems to require an astronomically large intermediate value, that is the signal to look for a counting argument instead.

Practice — real LeetCode problems

LC 66 — Plus One · Easy

Problem. Given a large integer as an array of its digits (most significant first, no leading zeros), increment it by one and return the resulting digit array.

Constraints. 1 <= len(digits) <= 1001 <= len(digits) <= 100, 0 <= digits[i] <= 90 <= digits[i] <= 9, and the number has no leading zeros.

Examples. [1,2,3][1,2,3] gives [1,2,4][1,2,4] · [4,3,2,1][4,3,2,1] gives [4,3,2,2][4,3,2,2] · [9][9] gives [1,0][1,0]

Editorial — approach, complexity, follow-ups

Increment the least significant digit and propagate a carry leftward. The instant a digit is below 9, adding one cannot carry, so you can return immediately.

Time $O(n)$ , and $O(1)$ for most inputs since it usually returns on the first digit. Space $O(1)$ if mutating in place, $O(n)$ for the all-nines case where a new list is created.

The test cases map to the distinct behaviours:

[1,2,3][1,2,3] — no carry at all; returns on the first iteration.
[1,9,9][1,9,9] gives [2,0,0][2,0,0] — carry propagates partway, then stops.
[9][9] and [9,9][9,9] — carry propagates all the way out, and the result is one digit longer. This is the case the final returnreturn exists for.
[0][0] gives [1][1] — the smallest input.

It is tempting to convert to an integer, add one, and split back into digits. In Python that works, since integers are unbounded — but it defeats the question, which exists precisely because the number may exceed native integer range in other languages. Mention it, then write the digit loop.

Follow-ups you should expect: “Add two digit arrays (LC 415)?” — the same carry logic with two inputs, walking both from the right. “Multiply them (LC 43)?” — accumulate result[i + j + 1] += a[i] * b[j]result[i + j + 1] += a[i] * b[j] into a len(a) + len(b)len(a) + len(b) buffer, then normalise carries in one pass. “Plus kk instead of one?” — add kk to the last digit and carry with divmoddivmod. “Digits stored least-significant-first?” — easier; you append rather than prepend, which is exactly LC 2’s representation.

LC 50 — Pow(x, n) · Medium

Problem. Implement pow(x, n)pow(x, n), which computes xx raised to the power nn.

Constraints. -100.0 < x < 100.0-100.0 < x < 100.0, -2^31 <= n <= 2^31 - 1-2^31 <= n <= 2^31 - 1, and either nn is non-zero or xx is non-zero. The answer is within 10^-410^-4 of the true value.

Examples. (2.0, 10)(2.0, 10) gives 1024.01024.0 · (2.1, 3)(2.1, 3) gives 9.2619.261 · (2.0, -2)(2.0, -2) gives 0.250.25

Editorial — approach, complexity, follow-ups

Write the exponent in binary. Since $x^{13} = x^{8} \cdot x^{4} \cdot x^{1}$ , you only need the powers of xx at powers of two — obtained by repeated squaring — multiplied together wherever the exponent has a set bit.

Time $O(\log n)$ multiplications. Space $O(1)$ iteratively (a recursive version is $O(\log n)$ stack).

Test-case notes: (2.0, 0)(2.0, 0) and (1.0, 0)(1.0, 0) both give 1.01.0, from resultresult being seeded at 1.01.0 and the loop never running. (2.0, -2)(2.0, -2) gives 0.250.25 via the reciprocal. (2.0, 1)(2.0, 1) is the single-bit case.

The recursive formulation is equally valid and some find it clearer: half = myPow(x, n // 2)half = myPow(x, n // 2), then half * halfhalf * half (times an extra xx if nn is odd). Same complexity, $O(\log n)$ stack.

Python’s built-in x ** nx ** n and pow(x, n)pow(x, n) do this for you — say so, then implement it, since the question is about the technique.

Follow-ups you should expect: “Modular exponentiation?” — add % MOD% MOD after each multiplication; that is pow(x, n, mod)pow(x, n, mod) built in, and the basis of RSA and of modular inverses. “Integer square root (LC 69)?” — binary search on the answer, or Newton’s method. “Matrix power?” — the identical algorithm with matrix multiplication, which computes Fibonacci in $O(\log n)$ . “Why not multiply nn times?” — $2^{31}$ operations at the stated limits.

LC 149 — Max Points on a Line · Hard

Problem. Given pointspoints on a 2D plane, return the maximum number of points that lie on the same straight line.

Constraints. 1 <= len(points) <= 3001 <= len(points) <= 300, -10^4 <= xi, yi <= 10^4-10^4 <= xi, yi <= 10^4, and all points are distinct.

Examples. [[1,1],[2,2],[3,3]][[1,1],[2,2],[3,3]] gives 33 · [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]][[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] gives 44 · [[1,1]][[1,1]] gives 11

Editorial — approach, complexity, follow-ups

Any line with at least two points contains some point as its “leftmost in iteration order”, so anchoring on every point in turn and grouping the later points by direction finds every line. The largest bucket plus the anchor is the answer.

Time $O(n^2)$ — each of nn anchors examines the remaining points, with $O(1)$ average dictionary work (plus a $\log$ factor for gcdgcd). Space $O(n)$ .

Three decisions carry the correctness:

Integer pairs, not floats. Dividing gives inexact values for ratios like 1/31/3; two different lines can then hash to the same float, or one line to two different floats. The normalised pair is exact.
Sign canonicalisation. Without it, (1,2)(1,2) and (-1,-2)(-1,-2) are distinct keys for the same direction. Since only later points are considered, this matters less than in the all-pairs formulation — but [[1,1],[2,2],[-1,-1]][[1,1],[2,2],[-1,-1]] is exactly the case that exposes it: anchored at [1,1][1,1], the directions to [2,2][2,2] and [-1,-1][-1,-1] are (1,1)(1,1) and (-2,-2)(-2,-2), which normalise to (1,1)(1,1) and (-1,-1)(-1,-1). Only the sign fix merges them, giving 33 rather than 22.
gcd(0, k) == abs(k)gcd(0, k) == abs(k). Vertical lines normalise to (0, 1)(0, 1) and horizontal to (1, 0)(1, 0) automatically. [[0,0],[0,1],[0,2]][[0,0],[0,1],[0,2]] gives 33 with no special case.

Only dx == dy == 0dx == dy == 0 would break it (gcd(0,0) == 0gcd(0,0) == 0 and the division raises), and that requires two identical points — which the constraints forbid. If duplicates were permitted you would count them separately and add them to every line through that position.

The len(points) <= 2len(points) <= 2 guard handles the single-point case, where the loop body never runs and best + 1best + 1 would still give 11 — but the explicit guard states the intent.

Follow-ups you should expect: “Why not floats?” — the most likely question; give the precision argument. “Handle duplicate points?” — count and add them separately. “Better than $O(n^2)$ ?” — no known general improvement; the problem is 3SUM-hard. “Are three points collinear?” — the cross product (x2-x1)*(y3-y1) - (y2-y1)*(x3-x1) == 0(x2-x1)*(y3-y1) - (y2-y1)*(x3-x1) == 0, which is exact, division-free, and the right primitive for convex-hull and area problems.

LeetCode problem set

#	Problem	Difficulty	The twist
66	Plus One	Easy	Early return on no-carry; prepend on all-nines
172	Factorial Trailing Zeroes	Medium	Count factors of 5; never compute the factorial
50	Pow(x, n)	Medium	Squaring driven by exponent bits; mind `-2^31-2^31`
43	Multiply Strings	Medium	Positional accumulation into a `m + nm + n` buffer, then carry
204	Count Primes	Medium	Sieve of Eratosthenes, marking from `i * ii * i`
149	Max Points on a Line	Hard	Normalised integer directions; never float slopes

Interview follow-ups

They ask	What they’re checking	The answer
“Why not use floats for slopes?”	The central trap	Precision makes distinct slopes compare equal; normalised integer pairs are exact and handle vertical lines
“Why normalise the sign?”	Care	`(1,2)(1,2)` and `(-1,-2)(-1,-2)` are the same direction but different dict keys, splitting one line into two buckets
“What about `gcd(0, 0)gcd(0, 0)`?”	Edge awareness	It is `00` and would raise — only possible with duplicate points, which the constraints exclude
“Why squaring rather than repeated multiplication?”	Complexity	$O(\log n)$ versus $O(n)$ ; at $n = 2^{31}$ that is decisive
“What breaks with `n = -2^31n = -2^31`?”	Reading constraints	Negating it overflows 32-bit signed; Python is immune but the constraint is there for a reason
“Convert digits to an int instead?”	Understanding the point	Works in Python, defeats the exercise, and fails where integers are fixed-width
“Are three points collinear?”	The right primitive	The cross product — exact and division-free

Edge-case checklist

All nines (LC 66) — [9][9], [9,9][9,9]; the answer grows a digit.
Partial carry — [1,9,9][1,9,9] gives [2,0,0][2,0,0].
Single digit zero — [0][0] gives [1][1].
Exponent zero (LC 50) — returns 1.01.0 for any xx.
Negative exponent — take the reciprocal.
n = -2^31n = -2^31 — the overflow case in fixed-width languages.
Base between 0 and 1 — (0.5, 2)(0.5, 2) gives 0.250.25; nothing assumes x > 1x > 1.
Single point (LC 149) — answer 11.
Vertical and horizontal lines — [[0,0],[0,1],[0,2]][[0,0],[0,1],[0,2]] gives 33; no division by zero.
Opposite-direction collinear points — [[1,1],[2,2],[-1,-1]][[1,1],[2,2],[-1,-1]] gives 33, the sign-canonicalisation test.
Negative coordinates — legal, and they are what make the sign convention necessary.

Recap

Digit arithmetic: process from the least significant end, return early when no carry is needed, and handle the case where the answer is longer than the input.
Exponentiation by squaring uses the exponent’s bits for $O(\log n)$ instead of $O(n)$ . Negative exponents take the reciprocal, and -2^31-2^31 is the overflow trap in fixed-width languages.
Never compare slopes as floats. Normalise (dx, dy)(dx, dy) by their gcdgcd and canonicalise the sign. gcd(0, k) == abs(k)gcd(0, k) == abs(k) makes vertical and horizontal lines work automatically.
For collinearity, the cross product is the exact, division-free primitive.
When a problem seems to need a huge intermediate value (a factorial, a giant power), look for a counting argument instead — LC 172 is four lines once you see it.
Read the constraints: mentions of $2^{31}$ are telling you about overflow and about the intended solution.

Next: Number Theory for Competitive Programming — sieves, modular inverses, and the identities worth memorising.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Math and Geometry Problems

What you’ll learn

The cue

Trap 1 — carry propagation

Trap 2 — exponentiation by squaring

Trap 3 — never compare slopes as floats

The variant map

Practice — real LeetCode problems

LC 66 — Plus One · Easy

LC 50 — Pow(x, n) · Medium

LC 149 — Max Points on a Line · Hard

LeetCode problem set

Interview follow-ups

Edge-case checklist

Recap

Was this page helpful?