LC Patterns — Math & Number Theory

Identities and routines to have at your fingertips

import math
math.gcd(a, b); math.lcm(a, b)          # lcm(a,b) = a*b // gcd(a,b)
math.comb(n, k); math.isqrt(n)          # exact integer nCr and √ — no float drift
pow(a, e, m)                            # fast modular exponentiation, O(log e)
pow(a, -1, m)                           # modular inverse (m prime or gcd(a,m)=1)
divmod(n, 10)                           # (n // 10, n % 10) — the digit-peeling idiom

• Euclid, two lines: while b: a, b = b, a % b — O(log min(a,b)). Bézout: ax + by = c solvable iff gcd(a,b) | c (this single fact is LC 365).
• Sieve of Eratosthenes: O(n log log n); mark from i*i, step i, only for prime i ≤ √n.
• Divisors pair around √n: enumerate i ≤ √n; each hit gives i and n // i. O(√n), and the perfect-square middle case appears once.
• MOD discipline: MOD = 10**9 + 7; reduce after every + and *. Division under mod does not exist — multiply by the modular inverse (Fermat: pow(a, MOD-2, MOD) since MOD is prime). Subtraction: (a - b) % MOD — fine in Python, needs +MOD first in C++/Java.

Python-specific gotchas (these decide bugs, learn them cold)

1. // floors toward −∞, C/Java truncate toward 0. -7 // 2 == -4 in Python, -7 / 2 == -3 in Java. LC 7 / 29 expect truncation → use int(a / b) or work with abs + sign. Same for %.
2. Floats lie. 0.1 + 0.2 != 0.3; math.sqrt on big ints drifts. Use math.isqrt, integer cross-multiplication (compare a*d vs b*c, not a/b vs c/d), and Fraction only if desperate.
3. Simulated 32-bit limits: INT_MAX = 2**31 - 1. Problems 7/8/29 require you to detect overflow that Python won't produce — check bounds explicitly and say so.

Universal pitfalls

1. Simulating what has a formula — the failure mode this whole file exists to prevent. If bounds exceed ~10⁸ operations, a formula/period/doubling is mandatory.
2. Modding too late or unevenly — one missed % MOD in a product chain is an overflow (other languages) or a wrong-answer-on-huge-case.
3. Edge integers: 0, 1, negatives, INT_MIN (whose absolute value overflows in C/Java — the classic 29 trap), n = 1 in "count/kth" problems.
4. Float equality anywhere — if you typed == between floats, redesign with integers.
5. Not testing the formula — after deriving, verify against brute force for n ≤ 8 mentally. A formula off by one at n=2 fails 100% of cases.

What it is: Process a number digit-by-digit without converting to a string (or while pretending not to): reverse an integer, test a numeric palindrome, add one with carries. The atomic moves: peel with n % 10, shrink with n // 10, build with rev = rev * 10 + d.

Intuition: a decimal number is a stack of digits — % 10 pops, // 10 shrinks, *10 + d pushes onto a new number in reversed order. Reversal is therefore pop-everything-push-everything. Palindrome (9): reverse only half the number and compare (rev >= n stops the loop) — avoids any overflow question and handles odd lengths by rev // 10. Plus one (66): carries propagate only through trailing 9s.

Approach: loop while n: n, d = divmod(n, 10). For LC 7's overflow spec: check rev > (INT_MAX - d) // 10 before the push (predict overflow, don't detect it after). Negatives: strip the sign, restore at the end.

What it is: Add or multiply numbers given as strings/arrays too large for fixed-width integers — reimplement the pencil-and-paper algorithms: right-to-left, per-position work, carry propagation.

Intuition: positional notation makes arithmetic local: position i of the result depends only on the input digits at/near i plus a carry. Addition: one zip from the right with a running carry. Multiplication (43): the key indexing fact — digit i × digit j lands in result positions i + j and i + j + 1 (from the right). Allocate len(a) + len(b) slots, accumulate raw products, then one carry-normalization pass.

Approach: addition template: two pointers from the ends, total = da + db + carry, emit total % base, carry = total // base, loop while i or j or carry, reverse at the end. Multiplication: res[i+j+1] += da*db double loop, then normalize carries right-to-left, strip leading zeros. Base 2 (67) is the same template with base = 2.

What it is: Problems whose hidden skeleton is the greatest common divisor: a common chunk size (strings, groups, decks), reachable water amounts with two jugs, synchronizing periodic events. Euclid's algorithm plus two facts — lcm = a·b/gcd and Bézout — cover all of them.

Intuition: gcd is "the largest unit both quantities are made of." String version (1071): if s + t == t + s the two strings are repetitions of one common block, and the answer's length is gcd(len(s), len(t)). Deck of cards (914): a valid group size must divide every count → feasible iff gcd(all counts) ≥ 2. Water jugs (365): every reachable amount is a Bézout combination ax + by, so the target is reachable iff target ≤ x + y and gcd(x, y) | target.

Approach: math.gcd / functools.reduce(gcd, counts) for the fold. Prove the string case both directions if asked: commuting concatenation ⇒ common period.

What it is: Anything needing many primality answers or prime factorizations: count primes below n, factor every element of an array, permutations constrained by primality. One precomputation — the sieve — converts per-query cost from O(√n) to O(1)-ish.

Intuition: primality of one number → trial division by candidates ≤ √n (any composite has a factor ≤ its square root). Primality of many numbers up to n → flip the direction: each prime announces its multiples — the sieve, O(n log log n). The upgrade: record for every number its smallest prime factor (SPF) during the sieve; then factoring any x is following SPF links — O(log x).

Approach: sieve template: is_prime = [True]*n, kill 0/1, for i in 2..isqrt(n): if prime, mark i*i, i*i+i, … False (starting at i*i because smaller multiples were killed by smaller primes). SPF variant: store spf[j] = i on first marking.

What it is: List, count, or sum the divisors of n — kth factor, perfect numbers, numbers with exactly four divisors. The single trick: divisors come in pairs (i, n/i) straddling √n, so full enumeration costs O(√n).

Intuition: if i | n then n/i | n, and one of the pair is ≤ √n — so scanning i = 1..⌊√n⌋ finds every divisor exactly once as the small half of its pair. Perfect square ⇒ i == n/i once — the self-paired middle. Formula view: if n = ∏ pᵢ^aᵢ, then #divisors = ∏(aᵢ+1) — knowing it lets you sanity-check (1390's "exactly four" means p·q or p³).

Approach: kth factor (1492): first pass over i ≤ √n collects small divisors counting toward k; second pass walks i back down, emitting large partners n//i in increasing order — skipping the middle when i*i == n. Perfect number (507): sum both halves of each pair, subtract n, compare.

What it is: Compute x^n (or anything defined by repeated combination) for astronomically large n by squaring: n halves every step, O(log n). Under a modulus, this plus modular inverses is the engine behind every "count … mod 10⁹+7" problem.

Intuition: x^n = (x²)^(n/2), times one extra x when n is odd — each squaring consumes one binary digit of the exponent. Read n in binary: x^13 = x^8 · x^4 · x^1. The same doubling computes division without / (29), matrix powers (Fibonacci in O(log n)), and repeated composition. Super pow (372): process the exponent's digits, or reduce with Fermat (a^b ≡ a^(b mod (p−1))).

Approach: iterative template (recite-able):

def power(x, n, m):
    res = 1
    x %= m
    while n:
        if n & 1: res = res * x % m
        x = x * x % m
        n >>= 1
    return res

Python's built-in pow(x, n, m) does exactly this — use it, but be ready to write it. Division under mod = multiply by pow(a, p−2, p) (Fermat, p prime).

What it is: "How many ways/paths/arrangements…" where the answer is a closed form: binomial coefficients, factorials, Catalan numbers, or a small product formula — often mod 10⁹+7. The skill is mapping the story onto a standard counting object.

Intuition: unique paths (62): every path is a shuffle of (m−1) downs and (n−1) rights → C(m+n−2, m−1). Pascal (118/119): C(n,k) = C(n−1,k−1) + C(n−1,k), and row generation in O(k) via the ratio C(n,k+1) = C(n,k)·(n−k)/(k+1). Pickup/delivery (1359): the i-th pair has (2i−1)·i valid slots → ∏ i·(2i−1), discovered by trying n=1,2 by hand. Recognize on sight: C(n,k), Catalan C(2n,n)/(n+1), stars-and-bars, inclusion–exclusion.

Approach: small/one-shot → math.comb. Under a modulus → precompute factorials fact[i] and inverse factorials inv_fact[i] = pow(fact[i], p−2, p) once, then C(n,k) = fact[n]·inv_fact[k]·inv_fact[n−k] % p in O(1). Always state the bijection.

What it is: Translate numbers between representations: decimal ↔ base-7, hex, Excel columns (base-26 without a zero), even base −2. The universal loop is divmod peeling; the interview content is in the irregular bases.

Intuition: standard base-b conversion is Pattern 1's digit peel with divmod(n, b). Excel columns (168/171) are the famous twist: digits run 1–26 with no zero — a bijective base-26. The fix is one line: subtract 1 before each divmod (n -= 1; n, r = divmod(n, 26)). Negative base (1017): same peel, but a negative remainder must be normalized up.

Approach: to-string: peel with divmod, append, reverse. From-string (171): Horner's rule left to right — n = n * 26 + val(c). For 168 recite "subtract one, then divide" and trace Z (26) and AA (27) by hand before submitting.

What it is: The answer is an algebraic identity away: Gauss sums, telescoping, rearranging an equation until the loop disappears. Missing number via expected-sum, counting odds in a range via prefix subtraction, expressing n as sums of consecutive integers.

Intuition: Gauss: 1+2+…+n = n(n+1)/2 — missing number (268) is expected − actual, one pass. Range counting (1523): define f(x) = count of odds in [0,x] = (x+1)//2, answer f(hi) − f(lo−1) — prefix-function subtraction works for any monotone count. Consecutive-sum (829): n = k·a + k(k−1)/2 ⇒ n − k(k−1)/2 must be positive and divisible by k; loop k while k(k−1)/2 < n → O(√n).

Approach: write the constraint as an equation; isolate the unknown; read off the iteration space and divisibility conditions. Keep everything in integers.

What it is: Repeatedly apply a digit-based map (sum of squared digits, sum of digits) until something stabilizes. Because the map crushes big numbers into a small range, the orbit must enter a cycle — detect it, or shortcut it with a known invariant.

Intuition: any n above a few hundred maps to something much smaller (sum of squared digits of a 13-digit number ≤ 13·81 = 1053), so all orbits fall into a bounded box and, by pigeonhole, eventually cycle. Happy number (202): a cycle means unhappy → detect with a seen-set or Floyd's tortoise-and-hare on the function. Digital root (258): the shortcut invariant — a number ≡ its digit sum mod 9 ⇒ answer is 1 + (n−1) % 9 for n > 0, O(1), no loop.

Approach: general template: iterate n = f(n) with a seen set until a fixed point or repeat. Upgrade 1: Floyd (O(1) space). Upgrade 2: a mathematical invariant that skips iteration (mod 9 for digit sums). Justify termination before the while-loop.

What it is: "Find the n-th number divisible by a / b / c" or "n-th magical number" — the k-th element of a merged multiples sequence, where n is too big to enumerate. Combine a counting function built from inclusion–exclusion with binary search on the answer.

Intuition: you can't list the sequence, but you can count it: numbers ≤ x divisible by a or b = x//a + x//b − x//lcm(a,b) (subtract the double-counted; for three sets, add back the triple term, and lcm not product). count(x) is monotone in x ⇒ the n-th element is the smallest x with count(x) ≥ n — a boundary search. This composition — NT gives the predicate, binary search finds the boundary — is the pattern.

Approach: write count(x) from inclusion–exclusion (2 or 3 terms); binary search lo = 1, hi = n · min(divisors); return lo % (10**9+7) if asked. Sanity-check count on tiny x by hand against a brute list.

What it is: Two players alternate moves, both playing optimally — who wins? The LC versions almost always collapse to a parity/invariant one-liner, and the interview is about finding it (via small cases) and proving it (via strategy or induction).

Intuition: work backward from losing positions. Nim (292): positions 1–3 win (take all), 4 loses (every move hands opponent 1–3), pattern locks in → n % 4 != 0; the proof is a strategy (whatever k the opponent takes, you take 4−k). Divisor game (1025): losing exactly when n is odd; parity is the invariant → n % 2 == 0. Stone game (877): with an even number of piles and unequal total, first player can commit to all-even or all-odd indexed piles → always true.

Approach: the method is the deliverable: (1) hand-compute win/lose for n = 1..8; (2) conjecture the pattern; (3) prove by exhibiting a strategy that preserves an invariant. If no clean pattern → it's a DP/minimax game, not a formula game.

What it is: The small set of geometry problems that actually appear: points on a line, rectangle overlap/union area, distances. The unifying rule: stay in integers — cross-multiplied slopes, squared distances, interval intersections — and float bugs become unrepresentable.

Intuition: max points on a line (149): anchor each point; every other point defines a direction — same line ⟺ same reduced slope. Represent slope as a canonical fraction (dy//g, dx//g) with g = gcd and a fixed sign — hashable, exact, no division. Rectangles (223/836): work per-axis — two boxes overlap iff they overlap on x and on y; 1-D overlap length is max(0, min(r1, r2) − max(l1, l2)); union area = A + B − overlap.

Approach: 149: double loop with a per-anchor hashmap of direction → count; normalize (dy, dx) by gcd and force a canonical sign. Rectangles: dx = max(0, …), dy = max(0, …); overlap strictness (836 wants positive area — > not ≥). Distances: compare squared distances.

What it is: Design-flavored randomness: pick an index proportionally to weights, build a fair rand10 from rand7, sample uniformly from a stream of unknown length. Each has one named technique, and each demands you prove uniformity, not just produce randomness. (Full treatment in probability.)

Intuition: weighted pick (528): lay the weights end-to-end as segments on a number line — prefix sums; a uniform dart r ∈ [1, total] lands in exactly one segment; find it with binary search — probability ∝ segment length by construction. rand10-from-rand7 (470): rejection sampling — two rand7 calls give a uniform 1..49; accept ≤ 40 and take % 10 + 1, else retry. Reservoir sampling (382): keep the i-th element with probability 1/i; P(item i survives) telescopes to 1/n.

Approach: 528: precompute the prefix array; per query bisect_left(prefix, randint(1, total)). 470: while-loop rejection; never "fix up" rejected values. 382: single pass, random.randint(1, i) == 1 → replace.