Math & Geometry

When to Use

• Large number operations (overflow, modular arithmetic)
• Prime number problems
• Grid transformations: rotate, spiral, zero-out
• GCD, LCM, factorial digit counting

Signal phrases: "count primes", "power of", "rotate matrix", "spiral", "trailing zeros", "modular", "GCD", "happy number"

---

Pattern 1 — Fast Exponentiation (Binary Exponentiation)

O(log N) instead of O(N). Halve the exponent at each step.

# LC 50 — Pow(x, n)
def myPow(x, n):
    if n < 0:
        x, n = 1 / x, -n
    result = 1
    while n:
        if n & 1:          # odd exponent — multiply result by current x
            result *= x
        x *= x             # square x
        n >>= 1            # halve exponent
    return result

# Modular fast power (prevents overflow in large-number problems)
def powMod(base, exp, mod):
    result = 1
    base %= mod
    while exp > 0:
        if exp & 1:
            result = (result * base) % mod
        base = (base * base) % mod
        exp >>= 1
    return result

Key rule: (a * b) % m == ((a % m) * (b % m)) % m — apply mod at every step.

---

Pattern 2 — Sieve of Eratosthenes

All primes up to N in O(N log log N).

# LC 204 — Count Primes
def countPrimes(n):
    if n < 2:
        return 0
    is_prime = [True] * n
    is_prime[0] = is_prime[1] = False

    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, n, i):   # start at i² — everything below already crossed off
                is_prime[j] = False

    return sum(is_prime)

Why start at i²? For prime i, any composite i*k where k < i was already crossed off by a smaller prime. So i*2, i*3, ... up to i*(i-1) are redundant.

---

Pattern 3 — Grid Transformations

# LC 48 — Rotate Image 90° clockwise — in-place, O(1) space
def rotate(matrix):
    n = len(matrix)
    # Step 1: Transpose (reflect across main diagonal)
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    # Step 2: Reverse each row
    for row in matrix:
        row.reverse()
    # 90° counter-clockwise: reverse rows first, then transpose

# LC 54 — Spiral Matrix — boundary shrink
def spiralOrder(matrix):
    result = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1

    while top <= bottom and left <= right:
        for c in range(left, right + 1):     result.append(matrix[top][c])
        top += 1
        for r in range(top, bottom + 1):     result.append(matrix[r][right])
        right -= 1
        if top <= bottom:
            for c in range(right, left - 1, -1): result.append(matrix[bottom][c])
            bottom -= 1
        if left <= right:
            for r in range(bottom, top - 1, -1): result.append(matrix[r][left])
            left += 1

    return result

# LC 73 — Set Matrix Zeroes — O(1) space using first row/col as markers
def setZeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    first_row = any(matrix[0][j] == 0 for j in range(n))
    first_col = any(matrix[i][0] == 0 for i in range(m))

    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][j] == 0:
                matrix[i][0] = matrix[0][j] = 0   # mark

    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0

    if first_row:
        for j in range(n): matrix[0][j] = 0
    if first_col:
        for i in range(m): matrix[i][0] = 0

---

Pattern 4 — GCD / LCM / Number Theory

import math

math.gcd(a, b)              # O(log min(a,b))
math.lcm(a, b)              # Python 3.9+
a * b // math.gcd(a, b)    # LCM manually

# Trailing zeros in N! — count factors of 5
def trailingZeroes(n):
    count = 0
    while n >= 5:
        n //= 5
        count += n    # n//5 + n//25 + n//125 + ...
    return count

# Happy Number — cycle detection via set
def isHappy(n):
    seen = set()
    while n != 1:
        if n in seen: return False
        seen.add(n)
        n = sum(int(d) ** 2 for d in str(n))
    return True

# Or: Floyd's cycle detection (O(1) space)
def isHappyFloyd(n):
    def next_num(x):
        return sum(int(d) ** 2 for d in str(x))
    slow, fast = n, next_num(n)
    while fast != 1 and slow != fast:
        slow = next_num(slow)
        fast = next_num(next_num(fast))
    return fast == 1

---

Python Math Utilities

import math

math.gcd(a, b)          # GCD
math.lcm(a, b)          # LCM (Python 3.9+)
math.isqrt(n)           # integer square root — no float error
math.factorial(n)       # N!
math.comb(n, k)         # C(n,k) — combinations
math.log(n, base)       # log base
math.inf                # infinity (also float('inf'))
pow(base, exp, mod)     # built-in modular fast power — faster than manual

---

Problems

---

Related

• [[DSA/DSA Techniques for Interviews/16. Bit Manipulation]] — binary math tricks
• [[DSA/DSA Techniques for Interviews/12. Dynamic Programming]] — counting bits uses DP
• [[DSA/DSA Topics]] — index