Math & Geometry

At a glance

The instinct

These problems look like puzzles but are usually one observation plus careful arithmetic. The observation is a property that survives the operations (a digit pattern, a count of prime factors, a slope, a midpoint). The arithmetic is where candidates lose points: 32-bit overflow, Java's negative remainders, and floating-point keys. The winning habit is to stay in integers for as long as possible: compare squared distances, store slopes as reduced fractions, and check overflow before multiplying.

Recognise it

Not this pattern if...

• The "math" is really counting arrangements with overlapping subproblems - that is DP or combinatorics.
• Points are only used as graph nodes (e.g. Min Cost to Connect All Points) - it is MST / graph.
• You need the k closest points - squared distance helps, but the pattern is a heap or quickselect.

Memory hack

Analogy: a carpenter measures twice and cuts once. Do the reasoning on paper (invariant), then do arithmetic only with exact tools (integers) - a floating-point ruler drifts.

Say it out loud in the interview:

1. "What stays the same / what am I really counting?" (factors of 5, equal slopes, shared midpoints)
2. "Can every value fit in int? Where could it overflow or go negative?"
3. "Edge cases: zero, negatives, Integer.MIN_VALUE, duplicate points, vertical lines."

How it works

Decide which tool from the problem's nouns:

flowchart TD
    A["Read the nouns"] --> B{"Digits of a number?"}
    B -->|"yes"| C["Peel with mod 10 and div 10, overflow check before multiply"]
    B -->|"no"| D{"Divisibility, factorial, primes?"}
    D -->|"yes"| E["Count prime factors, gcd or sieve; never build huge numbers"]
    D -->|"no"| F{"Points in the plane?"}
    F -->|"distances or shapes"| G["Squared distances, cross product, midpoints"]
    F -->|"collinear"| H["Slope as reduced dy/dx key per anchor point"]
    F -->|"no"| I["Look for a formula: sums, powers, binary search on answer"]

Two quick traces:

• Factorial Trailing Zeroes, n = 100: multiples of 5 contribute 20 fives, multiples of 25 contribute 4 more, 125 > 100 stops. Answer 24, without ever touching 100!.
• Max Points on a Line: from anchor (1,1), the points (2,2), (3,3) and (-1,-1) give dy/dx = 1/1, 2/2, -2/-2, which all reduce (sign normalised) to "1/1", so they land in one bucket.

Java template

class MathKit {
    // Reverse digits, returning 0 if the result leaves 32-bit range.
    static int reverse(int x) {
        int r = 0;
        while (x != 0) {
            int digit = x % 10;               // negative for negative x - that's fine here
            x /= 10;
            if (r > Integer.MAX_VALUE / 10 || (r == Integer.MAX_VALUE / 10 && digit > 7)) return 0;
            if (r < Integer.MIN_VALUE / 10 || (r == Integer.MIN_VALUE / 10 && digit < -8)) return 0;
            r = r * 10 + digit;
        }
        return r;
    }

    static int gcd(int a, int b) { return b == 0 ? Math.abs(a) : gcd(b, a % b); }

    // base^exp % mod in O(log exp).
    static long powMod(long base, long exp, long mod) {
        long result = 1 % mod;
        base %= mod;
        if (base < 0) base += mod;            // Java remainders can be negative
        while (exp > 0) {
            if ((exp & 1) == 1) result = result * base % mod;
            base = base * base % mod;
            exp >>= 1;
        }
        return result;
    }

    // Count of prime factor p in n! (p = 5 gives trailing zeros).
    static long factorInFactorial(long n, long p) {
        long count = 0;
        while (n > 0) { n /= p; count += n; }
        return count;
    }
}

class GeoKit {
    static long dist2(int[] a, int[] b) {
        long dx = a[0] - b[0], dy = a[1] - b[1];
        return dx * dx + dy * dy;             // exact, no sqrt
    }

    // > 0: o->a->b turns left, < 0: right, 0: collinear.
    static long cross(int[] o, int[] a, int[] b) {
        return (long) (a[0] - o[0]) * (b[1] - o[1]) - (long) (a[1] - o[1]) * (b[0] - o[0]);
    }

    // Canonical slope key between two distinct points.
    static String slopeKey(int[] a, int[] b) {
        int dx = b[0] - a[0], dy = b[1] - a[1];
        if (dx == 0) return "inf";            // vertical line
        if (dy == 0) return "0";              // horizontal line
        int g = MathKit.gcd(dx, dy);
        dx /= g; dy /= g;
        if (dx < 0) { dx = -dx; dy = -dy; }   // one sign convention
        return dy + "/" + dx;
    }
}

Complexity

Variations

• Digit manipulation - peel, rebuild, compare halves; reverse only half of the number to dodge overflow. Palindrome Number, Reverse Integer, Add Digits.
• Factor and divisor counting - count the limiting prime instead of forming the product. Factorial Trailing Zeroes, Count Primes (sieve).
• Fast operators - exponentiation by squaring, binary search for roots. Pow(x, n), Sqrt(x).
• Shape checks with distances - sort the 6 squared distances: 4 equal non-zero sides and 2 equal larger diagonals. Valid Square.
• Collinearity / slopes - reduced-fraction keys or cross product = 0. Max Points on a Line.
• Rectangles from diagonals - pairs with the same midpoint and length are diagonals of one rectangle. Minimum Area Rectangle II.
• Overlap tests - axis-aligned rectangles overlap when they overlap on both axes. Rectangle Overlap, Rectangle Area.

Common mistakes

• Math.abs(Integer.MIN_VALUE) is still negative; widen to long first or avoid abs on raw input.
• Java's % keeps the sign of the dividend (-7 % 10 == -7); normalise with ((x % m) + m) % m for modular math.
• Forgetting degenerate inputs: duplicate points in Valid Square (zero-length side), duplicate points in Max Points on a Line (they match every slope).
• Multiplying two int coordinates before casting - (long) (a * b) overflows first; write (long) a * b.
• Computing a huge intermediate (n!, a^b) instead of counting factors or reducing modulo as you go.

All practice problems

6 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.