Math

Math problems often look brute-force but have a number-theory shortcut. The key is to express the operation in terms of digits, factors, or invariants.

Pattern A: Palindrome by reversing half

Use when: you need to check if a number reads the same both ways.

Invariant: reversing half avoids overflow and ignores the middle digit.

Skeleton:

if n < 0 or (n % 10 == 0 and n != 0): return false
rev = 0
for n > rev:
    rev = rev*10 + n%10
    n /= 10
return n == rev or n == rev/10

Problems:

• palindrome-number.

Pattern B: Digit array increment

Use when: a number is stored as digits in an array.

Invariant: carry propagates until a non-9 digit is found.

Skeleton:

for i from end to start:
    if digits[i] < 9: digits[i]++; return digits
    digits[i] = 0
return [1] + digits

Problems:

• plus-one.

Pattern C: Count factors of 5

Use when: trailing zeros of n! are needed.

Invariant: each factor of 5 pairs with a factor of 2 to make a 10.

Skeleton:

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

Problems:

• factorial-trailing-zeroes.

Pattern D: Integer square root

Use when: you need floor(sqrt(x)) without floating error.

Invariant: mid*mid compares against x with overflow-safe division.

Skeleton:

lo = 0; hi = x
while lo <= hi:
    mid = (lo+hi)/2
    if mid <= x/mid: ans = mid; lo = mid+1
    else: hi = mid-1
return ans

Problems:

• sqrtx.

Pattern E: Fast exponentiation

Use when: you need x^n in O(log n).

Invariant: n's binary decomposition drives repeated squaring.

Skeleton:

if n < 0: x = 1/x; n = -n
res = 1
while n > 0:
    if n & 1: res *= x
    x *= x
    n >>= 1
return res

Problems:

• powx-n.

Pattern F: Slope normalization with GCD

Use when: you count collinear points.

Invariant: slope reduced by gcd is a unique key; duplicates are counted.

Skeleton:

for i in 0..n-1:
    map = {}
    dup = 1
    for j in i+1..n-1:
        dx = xj - xi; dy = yj - yi
        if dx == 0 and dy == 0: dup++; continue
        g = gcd(abs(dx), abs(dy))
        dx /= g; dy /= g
        normalize sign (dx < 0 or dx == 0 and dy < 0)
        map[(dx,dy)]++
    best = max(best, dup + max(map))

Problems:

• max-points-on-a-line.

When to use Math tricks (checklist)

• A direct simulation is too slow but a formula exists.
• You can reason about digits, factors, or invariants.

Common failures (checklist)

• Overflow when multiplying mid*mid or powers.
• Incorrect handling of negative numbers or zero.
• Not normalizing slopes consistently.

Problem mapping

• palindrome-number: reverse half.
• plus-one: carry propagation.
• factorial-trailing-zeroes: count factors of 5.
• sqrtx: integer binary search.
• powx-n: fast exponentiation.
• max-points-on-a-line: normalized slope counts.