Math & Geometry

8 questions, and the last section of the 150. Almost none of them are really about mathematics — they are about separating reading from writing, deriving an index map instead of guessing it, and noticing where the output doesn't fit the input's shape.

The three questions this section actually asks

The boundary bookkeeping in Spiral Matrix and the cycle framing in Happy Number are the two that stand apart, and both have a single crisp idea behind them.

Composing a transform out of simpler ones

A clockwise quarter turn is (i, j) → (j, n−1−i). Factor it:

transpose      (i, j) → (j, i)
reverse rows   (i, j) → (i, n−1−j)

Composed in that order, exactly the rotation — and both halves are trivially in place. The order is not interchangeable: reverse-then-transpose is the counter-clockwise turn, and it gives a different answer on about 85% of random matrices. Deriving that from the index map takes ten seconds; remembering it by rote is how people get it backwards.

Boundaries that move mid-iteration

The unvisited region is a rectangle, so four integers describe it. The trap is that top++ and right-- fire inside the ring, so the loop condition — checked once per ring — no longer holds by the third pass. Both the right-to-left and bottom-to-top passes need their own re-checks.

Measured: without them, 1,630 of 4,000 random shapes are wrong. A 3 × 5 returns 17 values instead of 15.

The invariant that catches every bug here: the output must have exactly m · n entries.

Deciding before writing

Clearing rows as you find zeros writes zeros that the same scan then reads as originals — the clearing cascades and the whole matrix goes to 0. So the algorithm is necessarily two-phase, and the O(1) version is that two-phase structure with the marker arrays relocated into row 0 and column 0.

Those two marker lines intersect at m[0][0], which is why one extra boolean is unavoidable, and why the apply phase must sweep bottom-up and right-to-left — the flags have to be the last cells overwritten.

And a sentinel value is not available: the constraints permit every int as a legal entry. Checking the value range before reaching for an out-of-band marker is the general habit.

Halving instead of counting

x^n = (x²)^(n/2) turns two billion multiplications into 32. The iterative form reads the exponent's binary digits, multiplying in base^(2^k) exactly when bit k is set.

The trap is Java-specific and shared with Reverse Integer: -Integer.MIN_VALUE is Integer.MIN_VALUE. Negating in int leaves the exponent negative, the loop never runs, and the function returns 1.0 for everything. long e = n; before the negation is the whole fix.

Note that x = 1.0 at that exponent returns 1.0 whether the code is right or wrong — so the base matters when picking the test case.

Place values, not pattern matching

a[i] is worth 10^(m−1−i) and b[j] is worth 10^(n−1−j), so their product is worth 10^(m+n−2−i−j) — index i+j+1 in a left-indexed array of length m+n, with the carry spilling into i+j.

Two facts fall out: the product has m+n or m+n−1 digits and never anything else (verified on 20,000 pairs), and the carry must accumulate rather than assign, since many (i, j) pairs share the same i+j. Measured: assignment is wrong on 14,219 of 20,000 pairs and still returns a plausible digit string.

Cycle detection wearing a disguise

f(n) = sum of squared digits is a function, so every trajectory is a tail leading into a cycle — which makes Happy Number structurally identical to Linked List Cycle.

The state space collapses immediately: a d-digit number maps to at most 81d, so the maximum over all 32-bit ints is 730, and after a second step everything is below 243. That bound is the termination proof, not an observation.

There is exactly one unhappy cycle — 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 — verified over every starting point in 1..1000, which every larger n reaches in two steps. That licenses the one-line while (n != 1 && n != 4), which is correct and which I'd still not submit: it depends on a constant the reader can't check, and the cubes-of-digits variant has several cycles.

Complexity

Every one is optimal. The matrix problems are O(cells) because every cell must be touched; the two numeric ones are logarithmic because halving is available.

The traps

Verification

Every snippet compiled and cross-checked against an independent reference — 90,000+ cases:

• Q1 across transpose-and-reverse and the layered four-way swap, against an O(n²)-space reference
• Q2 across the boundary version and peel-and-rotate, against a direction-simulation walker that shares none of the boundary logic
• Q3 across both the one-boolean and two-boolean variants, against an O(m+n)-space reference, on matrices with a quarter of cells zeroed
• Q4 across Floyd, a hash set and the n == 4 shortcut, on every value from 1 to 200,000
• Q5 across the early-return and explicit-carry forms, against BigInteger, with one in five inputs all-nines
• Q6 across iterative, recursive and naive, against Math.pow on 200,000 pairs — max relative error 3.5 × 10⁻¹⁵
• Q7 across the digit array and row-by-row partial products, against BigInteger, with one in seven having a zero operand
• Q8 across the frequency map and the row-indexed variant, against a direct count, on a 5 × 5 grid so that collisions and duplicates occur constantly

A second harness recomputes every numeric claim in the prose and all five diagrams, and differentially tests each alternate implementation shown in the files. Two of its own assertions were wrong on the first run — a count copied from a differently-seeded harness, and a malformed expression — which is a fair reminder that the test is code too.

Three measurement choices worth naming, because a lazier generator would have passed vacuously:

• Q3 uses a 25% zero density. With one zero per matrix the markers barely interact and every buggy variant passes.
• Q5 forces one in five inputs to be all-nines. Uniform random digit arrays essentially never produce the only case that matters.
• Q8 uses a 5 × 5 coordinate grid. On a large sparse grid random points almost never form squares, and the test would confirm nothing.