Core Concepts

Invariant — a quantity or property that does not change across all operations or steps in a process. If you can identify an invariant, you can determine what states are reachable from the initial state without simulating anything.

Monovariant — a quantity that only ever increases (or only decreases) under each operation. Monvariants prove termination and bound the number of steps; they are weaker than invariants (state is not fixed, just bounded).

Parity argument — reasoning about whether a quantity is odd or even. Many brainteasers reduce to: "this operation changes parity by X; can we ever reach parity Y from parity Z?"

Symmetry argument — if a problem is symmetric, an optimal or forced strategy can be derived by reflecting the opponent's moves or by observing that only one class of positions is distinguishable.

Coloring argument — assign labels (often two colors) to positions or elements; an operation that changes the label in a predictable way constrains reachability. Generalises parity.

Extremal principle — consider the element with the maximum (or minimum) value; argue that it cannot be affected by any operation, or must be affected first. Reduces the problem to a simpler sub-problem.

Counting / bijection — show a one-to-one correspondence between the set of solutions and a set that is easy to count. Turns a hard combinatorial question into a direct formula.

Strategy stealing — in two-player games, if position A is a guaranteed win for whoever moves first, and position B can move to A, then B is also a win. Piggybacks on the first player's advantage.

---

Types / Variants

---

Key Algorithms

Parity Check

Determine the answer by computing the parity of one or more parameters. O(1) time, O(1) space.

Key insight: if every valid operation changes a quantity by an even amount, then parity is preserved. If the target has different parity from the start, it is unreachable.

# Nim Game: first player wins iff n is not a multiple of 4
return n % 4 != 0

Symmetry-Based Game Strategy

For two-player games on a symmetric board, the first player wins by: (1) making any move that creates a symmetric position, then (2) mirroring every subsequent opponent move.

Key insight: after the first player creates symmetry, every move the second player makes has a mirror that the first player can always make. The second player runs out of moves first.

---

Problem Taxonomy

By Problem Category

Problem Signal → Technique

---

Common Patterns

---

Edge Cases & Pitfalls

• Jumping to simulation. The most common mistake: implementing a loop for n up to 10^9. If the answer only depends on n % k or on a closed-form property (perfect square, divisibility), simulation is unnecessary and will TLE. Always check for a cycle or closed form before coding a loop.

• Parity argument applied to the wrong quantity. Not every quantity in the problem has a useful parity. Identify specifically which quantity is preserved, not just "something is even/odd." Verify with 2-3 examples.

• Pigeonhole mis-application. Pigeonhole guarantees existence of a collision; it does not tell you which pigeons collide or how many. Do not use it to construct a specific answer — only to prove one exists.

• Off-by-one in cycle detection. When the cycle includes the starting state (0-indexed vs. 1-indexed period), returning n % k vs. (n - 1) % k + 1 can differ. Validate with n = k and n = k + 1.

• Symmetry argument failing on asymmetric boards. The mirror strategy only works when the board or state space is perfectly symmetric. If the first player's move breaks symmetry in a way that disadvantages them, the argument inverts.

• Assuming the problem is harder than it is. Brainteasers are intentionally disguised. If you have a clean O(1) idea that passes small cases, verify it rather than dismissing it as too simple.

• Integer overflow in modular arithmetic. For large n with cycle reasoning, compute n % k before any multiplication. In Python, overflow is not an issue, but in a conceptual solution it must be noted.

---

Implementation Notes

• Python's math.isqrt(n) gives the integer square root without floating-point error; prefer it over int(math.sqrt(n)) which can return n-1 for perfect squares near floating-point boundaries.
• When returning a boolean game result (first player wins / loses), verify both the base case and the recurrence before collapsing to n % k != 0.
• Python's arbitrary-precision integers make XOR accumulation safe for any bit-width; no overflow concern.
• For cycle-based problems, always hard-code the first few values rather than deriving them from a formula, then verify the formula matches.

---

Cross-Topic Relations

---

Interview Reference

Must-Know Problems

Parity / Modular

• Nim Game (LeetCode 292) — n % 4 != 0
• Bulb Switcher (LeetCode 319) — isqrt(n)
• Stone Game (LeetCode 877) — first player always wins (invariant proof)

Invariant / Reachability

• Reaching Points (LeetCode 780) — work backwards; invariant on (tx - ty) % sy
• Minimum Moves to Equal Array Elements (LeetCode 453) — incrementing n-1 elements equals decrementing one; answer is sum - n * min

Pigeonhole / Existence

• Find the Duplicate Number (LeetCode 287) — pigeonhole guarantees duplicate; Floyd's cycle (or binary search) finds it
• Couples Holding Hands (LeetCode 765) — greedy + parity on swap count

Symmetry / Game

• Stone Game II / III — verify brute-force DP matches the parity pattern, then collapse
• Flip Game II (LeetCode 294) — memoised game; illustrates when parity alone is insufficient

Clarification Questions to Ask

• "Is n guaranteed to be positive, or can it be zero?" — changes base case for parity arguments.
• "Are values guaranteed distinct?" — affects whether pigeonhole applies directly.
• "Is optimal play defined as maximising score or just winning/losing?" — changes the game-theory model needed.
• "Can I modify the input array?" — relevant for in-place XOR solutions.

Common Interview Mistakes

• Implementing O(n) or O(n log n) simulation when an O(1) formula exists; the interviewer expects the insight, not the brute-force.
• Proving correctness for the pattern by example only ("it works for n = 1,2,3") without arguing why it holds in general.
• Conflating "the first player can always win" (strategy exists) with "the first player wins regardless of opponent moves" (the strategy is deterministic).
• Not checking the edge case n = 0 or n = 1 before applying the general formula.
• Stating the invariant vaguely ("something is always even") without naming the exact quantity.

Typical Follow-Up Escalations

• "Now solve it if there are 3 players instead of 2." — Nim theory generalises; Sprague-Grundy applies. Expected: re-derive the losing positions.
• "Can you prove the formula rather than just pattern-match?" — Expected: state the invariant explicitly and show it is preserved by every valid move.
• "What if the range of values is not 1..n?" — Pigeonhole still applies if the range size is smaller than the count; reformulate.
• "What is the minimum number of operations to reach the target?" — Shifts from reachability to monovariant bounding; expected: show the monovariant decreases by exactly 1 per step.