Math and Geometry — How the Pattern Works
Math and Geometry patterns replace imprecise floating-point operations, overflow-prone type conversions, and exhaustive step-by-step simulations with exact integer invariants, coordinate projections, and closed-form number-theoretic identities. Maintaining exactness—by cross-multiplying slopes, comparing squared Euclidean distances, projecting axis-aligned shapes onto independent 1D intervals, and propagating carries across base-k digit streams—eliminates precision and boundary bugs. Combined with structural reductions such as GCD/LCM inclusion-exclusion, modular invariants, 45-degree Manhattan rotation, and binary exponentiation, these techniques routinely collapse O(n^3) or O(n^2) geometric searches to O(n log n) or O(n) and reduce O(n) or O(2^n) simulations to O(log n) or O(1).
- 2D point sets asking for collinearity, turn orientation, convex hulls, or circle/polygon containment where floating-point division or square roots risk rounding errors or division-by-zero exceptions.
- Axis-aligned rectangles, Manhattan distances (|x1 - x2| + |y1 - y2|), or king-move Chebyshev distances (max(|dx|, |dy|)) that decouple into independent 1D intervals or rotated (x + y, x - y) coordinates.
- Arbitrarily long integers represented as strings, arrays, or linked lists—or signed 32-bit integers with overflow constraints—requiring right-to-left column addition or mod/div digit extraction.
- Divisibility, repeating patterns, base conversions, prime counting, large exponents, or deterministic game states governed by GCD/LCM, Bézout's identity, sieves, or exponentiation by squaring.
- Monotonic counting formulas (e.g., multiples up to x) suitable for binary search on the answer, or tiny point sets (n <= 10) where O(n^3) enumeration or O(2^n * n^2) bitmask DP is optimal.
- Using floating-point division or square roots for exact geometry: dy / dx crashes on vertical lines (dx == 0) and rounds repeating decimals, while math.sqrt(n) loses integer precision on large inputs; prefer cross-multiplication, GCD-normalized integer pairs, dx*dx + dy*dy, and math.isqrt(n).
- Confusing strict interior vs. boundary inequalities: edge-touching rectangles have zero overlap area (require left < right), whereas points on a circle's boundary count as inside (dx^2 + dy^2 <= r^2) and collinear fence vertices require popping only on cross < 0 rather than cross <= 0.
- Dropping final carries, mischecking 32-bit overflow, or mishandling zero/negatives: omitting 'or carry' in digit loops fails on 99 + 1, testing result * 10 + digit > limit overflows before the comparison instead of result > (limit - digit) // 10, and n == 0 requires explicit base cases in base conversion, digital roots, and power checks.
- Overlooking coincident points and 1-based indexing shifts: four identical points yield six zero distances in Valid Square unless dist[0] > 0 is enforced, observer-coincident points have undefined atan2(0, 0) angles in visibility sweeps, and 1-indexed divisor positions require reading nums[i - 1].
import math
def cross(o, a, b):
return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
def canonical_slope(x0, y0, x1, y1):
dx, dy = x1 - x0, y1 - y0
g = math.gcd(dx, dy)
dx, dy = dx // g, dy // g
if dx < 0 or (dx == 0 and dy < 0):
dx, dy = -dx, -dy
return (dy, dx)def add_digit_streams(a, b, base=10):
i, j, carry, out = len(a) - 1, len(b) - 1, 0, []
while i >= 0 or j >= 0 or carry:
total = carry + (a[i] if i >= 0 else 0) + (b[j] if j >= 0 else 0)
carry, digit = divmod(total, base)
out.append(digit)
i, j = i - 1, j - 1
return out[::-1]def fast_pow(x, n):
if n < 0:
x, n = 1 / x, -n
result = 1
while n > 0:
if n & 1:
result *= x
x *= x
n >>= 1
return result