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:

1. Carry propagation. Digit-by-digit arithmetic where the answer can be longer than the input.
2. Exponentiation. Multiplying n times is $O(n)$; squaring is $O(\log n)$ — and negative exponents plus one asymmetric edge case are where submissions fail.
3. 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.
• gcd 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

You are looking at a math or geometry problem when…

• Numbers are given as digit arrays or strings, usually because they are too large for a native integer — 66, 43, 415, 2.
• You need a power, a root, or a modular result — 50, 69, 372.
• Points, lines, slopes, areas — 149, 587, 963.
• Counting a property of factorials or divisors — 172, 204.
• The constraints mention $2^{31} - 1$ or “the answer fits in 32 bits” — that is a hint about overflow, which matters even in Python for reasoning about the intended solution.

Visual intuition

Most of this page is about avoiding a trap rather than running an algorithm, but one genuine algorithm shows up constantly in the maths problems — the sieve. Watch the stride: the inner loop jumps by i and starts at i², which is what separates it from a scan.

bitsThe sieve never tests a number — it crosses off multiplesO(n log log n)

00112233445566778899101011111212131314141515161617171818191920202121222223232424252526262727282829293030

1def sieve(n):2    is_prime = [True] * (n + 1)3    is_prime[0] = is_prime[1] = False4    for i in range(2, int(n ** 0.5) + 1):5        if is_prime[i]:6            for j in range(i * i, n + 1, i):   # start at i*i, stride by i7                is_prime[j] = False8    return [i for i, p in enumerate(is_prime) if p]

n30marks0

initEvery number from 0 to 30 starts assumed prime, except 0 and 1 which are special-cased. The sieve does not test any number for primality — it crosses off multiples, which is why it beats trial division for bulk queries.

Play‹›1/6⟲

Two things worth pausing on. The inner loop starts at i² rather than 2i, because every smaller multiple of i has a factor below i and was crossed off in an earlier round. And the outer loop stops at √30, since any composite up to 30 must have a factor at or below its square root.

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

The early return 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.

The all-nines case is the entire problem

[9] must give [1,0], and [9,9] must give [1,0,0]. The answer is longer than the input, which is what a naive in-place-only solution cannot express.

Reaching the return [1] + digits line means every digit has been set to 0, so prepending 1 produces the right power of ten. Forgetting it returns [0] for [9], which is silently wrong.

The same shape drives multi-digit addition (LC 415, LC 2) and multiplication (LC 43): process from the least significant end, carry forward, and handle a final carry after the loop.

Trap 2 — exponentiation by squaring

Computing x^n by multiplying n 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

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

The negative-exponent asymmetry, and why Python spares you

n can be -2^31, whose negation 2^31 overflows a 32-bit signed integer. In C++ or Java you must handle it — typically by using a 64-bit type, or by peeling off one multiplication before negating.

Python’s integers are arbitrary-precision, so -n is simply fine. But knowing why the constraint -2^31 <= n <= 2^31 - 1 is stated that way is exactly the kind of detail that distinguishes someone who has thought about the problem.

The same recurrence with % MOD after each multiplication is modular exponentiation, the workhorse of competitive programming — and Python has it built in as pow(x, n, mod). Worth naming; see Number Theory.

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

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/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)

Two details make this correct

Canonicalise the sign. Without it, (1, 2) and (-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 > 0, and dy > 0 when dx == 0, gives each direction exactly one representative.

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

The one input that would break it is dx == dy == 0, since gcd(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)	$O(n)$ multiplications	$O(\log n)$ by squaring
Max points on a line	$O(n^3)$ triples	$O(n^2)$ slope buckets per anchor

Dry run

Carry propagation — plus_one([1, 2, 9]). Walk from the right, and stop at the first digit below 9:

index	digit	action
2	9	it is 9 → set to 0, carry continues
1	2	below 9 → increment to 3 and return immediately

Result [1, 3, 0]. The early return is the point: the loop only runs while there is a carry, so the common case costs one iteration, not n.

The all-nines case is the one that needs the line after the loop: [9, 9] → both become 0, the loop ends with the carry still live, and the answer is [1] + digits = [1, 0, 0] — one digit longer than the input. Forgetting that line returns [0, 0], which is the standard failure and the only input that exposes it.

Exponentiation by squaring — my_pow(2.0, 10). 10 = 1010₂:

n	bit	x (squared each round)	result
10	0	2	1 — bit clear, nothing multiplied in
5	1	4	4
2	0	16	4
1	1	256	1024

Four iterations rather than ten multiplications, and $2^{10} = 4 \times 256$ — the two set bits pick exactly $2^2$ and $2^8$. For n = 2^31 the naive loop is two billion multiplications and this is 31.

• Negative exponents are handled once, up front: x, n = 1/x, -n. Doing it inside the loop, or forgetting n = -n, gives an infinite loop rather than a wrong answer.
• n = -2^31 is the edge case that overflows in fixed-width languages, because -(-2^31) does not fit. Python is immune, but it is worth naming.

Slopes as integer pairs — points (1,1), (2,2), (3,3), (1,2). Taking (1,1) as the anchor:

to	(dx, dy) raw	÷ gcd	canonical key
(2,2)	(1, 1)	(1, 1)	(1, 1)
(3,3)	(2, 2)	(1, 1)	(1, 1) — same key, so collinear ✓
(1,2)	(0, 1)	(0, 1)	(0, 1) — vertical, no division by zero

• The float version gets this right and still cannot be trusted. 1/3 == 2/6 happens to hold in IEEE 754, but 0.1 + 0.2 == 0.3 does not — so “it worked on my test case” proves nothing. The integer pair is exact by construction, which is a different kind of correct.
• The vertical line is free. dx = 0 produces the key (0, 1) with no special case, where the division form raises ZeroDivisionError.
• Sign canonicalisation is not cosmetic. Without it (1, 2) and (-1, -2) — the same direction — become different dictionary keys, and collinear points get split across two buckets.

Complexity

Problem	Time	Space	Note
Plus One / add strings	$O(n)$	$O(1)$ extra	early return makes the common case $O(1)$
LC 50 pow(x, n)	$O(\log n)$	$O(1)$ iterative, $O(\log n)$ recursive	naive is $O(n)$
LC 204 Count Primes	$O(n \log\log n)$	$O(n)$	per-number trial division is $O(n\sqrt n)$
Single primality test	$O(\sqrt n)$	$O(1)$	do not build a sieve for one query
LC 149 Max Points on a Line	$O(n^2)$	$O(n)$	a slope map per anchor point
LC 48 Rotate Image	$O(n^2)$	$O(1)$	transpose, then reverse each row
LC 54 Spiral Matrix	$O(mn)$	$O(1)$ beyond output	four shrinking boundaries
LC 202 Happy Number	$O(\log n)$ per step	$O(1)$	fast/slow pointers on a functional graph
LC 66/43 big-number arithmetic	$O(n)$ / $O(nm)$	$O(n + m)$	digit arrays, because the value does not fit

Two observations worth carrying:

• The $\sqrt n$ / $\log n$ / $\log\log n$ distinctions are the whole game here. Trial division to $\sqrt n$, exponentiation in $\log n$, a sieve in $n \log\log n$ — each replaces a linear or exponential loop, and picking the wrong one is what makes these problems time out rather than fail.
• Geometry answers are usually $O(n^2)$ and that is fine. LC 149 tries every point as an anchor, which is intended: with $n \le 300$ the quadratic is the expected solution, and reaching for something cleverer is a misread of the constraints.

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!	Count factors of 5	172
Count primes	Sieve of Eratosthenes	204
Convex hull / area	Cross products, never slopes	587 · 963

LC 172 is the one that rewards thinking over coding

Factorial Trailing Zeroes asks how many zeros end n!. Computing n! is impossible for large n — 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!:

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) <= 100, 0 <= digits[i] <= 9, and the number has no leading zeros.

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

pch.exerciseTag pch.exerciseTitle

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] — no carry at all; returns on the first iteration.
• [1,9,9] gives [2,0,0] — carry propagates partway, then stops.
• [9] and [9,9] — carry propagates all the way out, and the result is one digit longer. This is the case the final return exists for.
• [0] gives [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] into a len(a) + len(b) buffer, then normalise carries in one pass. “Plus k instead of one?” — add k to the last digit and carry with divmod. “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), which computes x raised to the power n.

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

Examples. (2.0, 10) gives 1024.0 · (2.1, 3) gives 9.261 · (2.0, -2) gives 0.25

pch.exerciseTag pch.exerciseTitle

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 x 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) and (1.0, 0) both give 1.0, from result being seeded at 1.0 and the loop never running. (2.0, -2) gives 0.25 via the reciprocal. (2.0, 1) is the single-bit case.

The overflow detail worth mentioning

n can be -2^31, and -(-2^31) = 2^31 overflows a 32-bit signed integer. Python is immune because its integers are unbounded, but the constraint is written that way deliberately — in C++ or Java you would use a 64-bit type for the exponent, or peel one multiplication off before negating.

Raising this unprompted signals that you read the constraints and understood why they say what they say.

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

Python’s built-in x ** n and 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 after each multiplication; that is 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 n times?” — $2^{31}$ operations at the stated limits.

LC 149 — Max Points on a Line · Hard

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

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

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

pch.exerciseTag pch.exerciseTitle

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 n anchors examines the remaining points, with $O(1)$ average dictionary work (plus a $\log$ factor for gcd). Space $O(n)$.

Three decisions carry the correctness:

• Integer pairs, not floats. Dividing gives inexact values for ratios like 1/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) and (-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]] is exactly the case that exposes it: anchored at [1,1], the directions to [2,2] and [-1,-1] are (1,1) and (-2,-2), which normalise to (1,1) and (-1,-1). Only the sign fix merges them, giving 3 rather than 2.
• gcd(0, k) == abs(k). Vertical lines normalise to (0, 1) and horizontal to (1, 0) automatically. [[0,0],[0,1],[0,2]] gives 3 with no special case.

Only dx == dy == 0 would break it (gcd(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) <= 2 guard handles the single-point case, where the loop body never runs and best + 1 would still give 1 — 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, which is exact, division-free, and the right primitive for convex-hull and area problems.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

LC 43 is the carry pattern at full strength

Multiply Strings forbids converting to integers. The clean approach is positional: allocate a buffer of length len(a) + len(b), and for every pair of digits add a[i] * b[j] into position i + j + 1. Only after all products are accumulated do you sweep once from the right normalising carries.

Separating “accumulate” from “carry” is what keeps it manageable — trying to carry during accumulation multiplies the bookkeeping. Then strip leading zeros, and remember "0" * anything must return "0" rather than an empty string.

Same three ingredients as LC 66: process from the least significant end, defer the carry, and handle the leading-digit edge case.

9 problems

1 easy6 medium2 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

AllEasyMediumHard

Unsolved onlyExportImportReset

• ○66Plus OneeasyEarly return on no-carry; prepend on all-ninesNeetCode 150LeetCode Top Interview 150
• ○7Reverse IntegermediumNeetCode 150
• ○43Multiply StringsmediumPositional accumulation into a `m + n` buffer, then carryNeetCode 150
• ○50Pow(x, n)mediumSquaring driven by exponent bits; mind `-2^31`NeetCode 150LeetCode Top Interview 150
• ○172Factorial Trailing ZeroesmediumCount factors of 5; never compute the factorialLeetCode Top Interview 150
• ○204Count PrimesmediumSieve of Eratosthenes, marking from `i * i`
• ○2013Detect SquaresmediumNeetCode 150
• ○149Max Points on a LinehardNormalised integer directions; never float slopesLeetCode Top Interview 150
• ○233Number of Digit Onehard

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) and (-1,-2) are the same direction but different dict keys, splitting one line into two buckets
“What about gcd(0, 0)?”	Edge awareness	It is 0 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^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]; the answer grows a digit.
• Partial carry — [1,9,9] gives [2,0,0].
• Single digit zero — [0] gives [1].
• Exponent zero (LC 50) — returns 1.0 for any x.
• Negative exponent — take the reciprocal.
• n = -2^31 — the overflow case in fixed-width languages.
• Base between 0 and 1 — (0.5, 2) gives 0.25; nothing assumes x > 1.
• Single point (LC 149) — answer 1.
• Vertical and horizontal lines — [[0,0],[0,1],[0,2]] gives 3; no division by zero.
• Opposite-direction collinear points — [[1,1],[2,2],[-1,-1]] gives 3, the sign-canonicalisation test.
• Negative coordinates — legal, and they are what make the sign convention necessary.

Self-check

pch.quizTag Math and geometry — self-check

1. Why represent a slope as a normalised integer pair rather than a float?

   A Floats are slower B Because division by zero on vertical lines and floating-point inexactness both make comparisons unreliable — the reduced (dx, dy) pair is exact by construction C Because tuples hash faster D Because slopes can exceed the float range
   pch.quizShowAnswer

   B — Because division by zero on vertical lines and floating-point inexactness both make comparisons unreliable — the reduced (dx, dy) pair is exact by construction — `1/3 == 2/6` happens to hold in IEEE 754, which is exactly why a passing test proves nothing — `0.1 + 0.2 == 0.3` is False. Exactness by construction is a different guarantee from 'it worked here'.

2. After dividing (dx, dy) by their gcd, why canonicalise the sign?

   A To keep dx positive for readability B Because (1, 2) and (-1, -2) are the same direction but different dictionary keys — without canonicalisation collinear points get split across two buckets C To avoid negative zero D It is optional
   pch.quizShowAnswer

   B — Because (1, 2) and (-1, -2) are the same direction but different dictionary keys — without canonicalisation collinear points get split across two buckets — The vertical case needs the tie-break too: when dx == 0, force dy positive, or (0,1) and (0,-1) diverge.

3. In `plus_one`, which input exposes the missing line after the loop?

   A [0] B All nines — [9,9] must return [1,0,0], one digit LONGER than the input; without the final `[1] + digits` it returns [0,0] C A single-digit input D An empty list
   pch.quizShowAnswer

   B — All nines — [9,9] must return [1,0,0], one digit LONGER than the input; without the final `[1] + digits` it returns [0,0] — Every other input returns early from inside the loop, so the trailing line only ever runs on all-nines. That is why it is both easy to omit and easy to miss in testing.

4. Exponentiation by squaring computes 2^10 in four iterations. Where do the multiplications happen?

   A Once per iteration B Only on set bits of the exponent — 10 is 1010₂, so the result picks up x² and x⁸ while the base is squared unconditionally every round C Only at the end D Once per bit of the base
   pch.quizShowAnswer

   B — Only on set bits of the exponent — 10 is 1010₂, so the result picks up x² and x⁸ while the base is squared unconditionally every round — The unconditional squaring is what makes the base hold x^(2^k) at round k; the bits select which of those rungs get multiplied in. 4 × 256 = 1024.

5. You need to know whether one number around 10^12 is prime. Sieve?

   A Yes, that is what sieves are for B No — trial division to √n is about 10^6 operations, whereas a sieve of that size cannot even be allocated. Sieves are for bulk queries C Yes, but only up to √n D Use Fermat's little theorem
   pch.quizShowAnswer

   B — No — trial division to √n is about 10^6 operations, whereas a sieve of that size cannot even be allocated. Sieves are for bulk queries — Matching the tool to the query count is the recurring decision on this page: √n for one, n log log n for all of them up to n.

6. LC 149 (max points on a line) is O(n²). Is that a problem?

   A Yes, it should be O(n log n) B No — trying every point as an anchor is the intended solution, and with n ≤ 300 the quadratic is what the constraints are signalling C Yes, use a convex hull D Only if the points are unsorted
   pch.quizShowAnswer

   B — No — trying every point as an anchor is the intended solution, and with n ≤ 300 the quadratic is what the constraints are signalling — Reading the constraints backwards to infer the intended complexity works here as elsewhere: n ≤ 300 rules out any need for cleverness beyond the per-anchor slope map.

Recall card

• Cue — the problem is arithmetic or geometric rather than structural: digits, powers, primes, points, rotations, spirals.
• Never compare slopes as floats. Reduce (dx, dy) by gcd, then canonicalise the sign. Exact, and vertical lines need no special case.
• Carry problems walk from the right, return early when a digit is below 9, and need the [1] + digits line for the all-nines case.
• Powers — exponentiation by squaring, $O(\log n)$: square the base every round, multiply into the result on set bits. Handle a negative exponent once, up front.
• Primes — a sieve for many queries ($O(n\log\log n)$, inner loop starts at i², outer stops at $\sqrt n$); trial division to $\sqrt n$ for one.
• Matrix in place — rotate = transpose then reverse each row; spiral = four shrinking boundaries.
• Big values — keep digits in an array; the point of these problems is that the number does not fit.
• Expect $O(n^2)$ in geometry and read the constraints before trying to beat it.

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 is the overflow trap in fixed-width languages.
• Never compare slopes as floats. Normalise (dx, dy) by their gcd and canonicalise the sign. 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.