Math and Game
What is this?
A hundred bulbs, a hundred rounds of toggling, and the question is how many end up on. You could simulate it with about n ln n toggles, replaying every round. Or you could notice that bulb k is flipped once for each of its divisors, that divisors come in pairs, and that only a perfect square has an unpaired one. The answer is floor(sqrt(n)), and the simulation was never needed.
Every problem here is that shape. The work is finding the structural fact, and once you have it there is almost no code.
Fun fact: Nim Game with the "take 1 to 3 stones" rule is decided entirely by
n % 4. If the pile is a multiple of four you lose against perfect play, because whatever you take (1, 2 or 3), your opponent takes the complement (3, 2 or 1) and restores a multiple of four. The pile shrinks by exactly four each round until you face zero. The whole solution isreturn n % 4 != 0, and the reasoning takes longer to say than the code takes to write.
🔓 The 7 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core idea: work out what the answer must be from the structure (how many times something is toggled, how each bit position contributes, which positions are lost regardless of play) instead of simulating the process described.
1. Counting per position instead of per pair
Total Hamming Distance sums the bit differences over every pair of numbers. With n up to 10⁴ that is 50 million pairs, and there is no need to enumerate them.
Look at one bit position in isolation. If k of the n numbers have a 1 there, then every one of those k differs from each of the n − k numbers with a 0, contributing k × (n − k) to the total. Bits are independent, so:
total = 0
for bit in range(32):
ones = sum((x >> bit) & 1 for x in nums)
total += ones * (len(nums) - ones)
return total
O(32n) instead of O(n²). The decomposition, each position contributes independently, is the transferable idea, not the code.
2. Losing positions
For a two-player game with optimal play, work out which positions lose. With stones and moves of 1–3, position 0 is a loss for whoever must move. Positions 1, 2 and 3 are wins (take everything). Position 4 is a loss, because every move leaves the opponent a winning position. The pattern repeats every four.
3. Grouping by a common divisor
X of a Kind in a Deck of Cards asks whether the cards can be split into equal groups of size at least 2. Count each value's frequency; a valid group size must divide every frequency, so the question is whether the GCD of all the frequencies is at least 2.
4. A 30-second worked example (Total Hamming Distance)
nums = [4, 14, 2] → binary 00100, 01110, 00010
Check by brute force: d(4,14) = 2, d(4,2) = 2, d(14,2) = 2 → 6 ✓. The per-bit sum agrees, and it never looked at a pair.
5. Where you'll actually meet this
- Pairwise totals. Summing a pairwise difference over a large set is usually done by counting how many items fall on each side of a split, not by visiting every pair.
- Error-correcting codes. Hamming distance is the basic metric for error-detecting and error-correcting codes.
- Combinatorial games. Losing-position analysis decides optimal play in small take-away games like Nim.
- Packing. A GCD of the tallies tells you whether items divide evenly into equal batches.
- Layout. Fitting a fixed number of cells into the most square grid is the same search as Construct the Rectangle.
6. Problems in this chapter
Bulb Switcher
How many bulbs remain on after n rounds of toggling. Divisors pair except for perfect squares, so the answer is floor(sqrt(n)).
Pattern: divisor parity. Target: O(1) time with math.isqrt.
Total Hamming Distance
Sum of bit differences over all pairs. Count ones per bit position and add ones × zeros.
Pattern: per-position decomposition. Target: O(32n) time, O(1) space.
Nim Game
Can the first player win taking 1–3 stones? Lose exactly when the count is a multiple of four.
Pattern: losing-position invariant. Target: O(1) time.
X of a Kind in a Deck of Cards
Can the deck be split into equal groups of at least two? Take the GCD of all value frequencies.
Pattern: GCD over frequencies. Target: O(n) time.
Can Make Arithmetic Progression From Sequence
Can the values be reordered into an arithmetic progression? Sort and check that consecutive differences are equal.
Pattern: sort then verify, or compute the gap from min and max. Target: O(n log n) time with a sort, O(n) with the min/max route.
Construct the Rectangle
Most square L × W with L · W = area and L >= W. Walk W down from floor(sqrt(area)) to the first divisor.
Pattern: divisor search from the square root. Target: O(sqrt(area)) time.
Mirror Reflection
Which receptor a laser in a mirrored square reaches first. Unfold the reflections into a straight line, divide p and q by their gcd, and read the answer off their parities.
Pattern: unfolding plus parity. Target: O(log(min(p, q))) time.
7. Common pitfalls
- Simulating the bulbs. About
n ln nwork when the answer is a square root. - Enumerating pairs for Hamming distance. The per-bit decomposition exists exactly to avoid it.
- Fixing the bit width at 32 without checking. Fine for non-negative 32-bit values, but say so.
- Starting the rectangle search at 1. Start at
floor(sqrt(area))and walk down; the first divisor found is the most square. - Forgetting the group size must be at least 2 in the card problem. A GCD of 1 means impossible.
- Checking the gaps in the given order for the arithmetic-progression problem. The input is unordered, so either sort first or compute the gap from min and max.
- Assuming the Nim rule. The multiple-of-four result depends on the "1 to 3" move set; a different move set gives a different invariant.
- Simulating the bounces in Mirror Reflection. Unfold the reflections instead: after dividing out the gcd, the parities of
pandqdecide the receptor.
8. Key takeaways
- Reason to the answer. Ask what it must be before deciding how to compute it.
- Divisors pair, so squares are the exception, the observation behind an entire family of puzzles.
- Decompose into independent positions and a quadratic count becomes linear.
- Games are decided by losing positions, found by working up from zero.
- A GCD answers "can these be grouped evenly?"
- Search divisors from the square root when you want the most balanced factor pair.
- Unfold reflections into a straight line and the bounces become a parity check.
- Why interviewers use these: they cannot be pattern-matched, so they reveal whether you probe a problem's structure or reach for a data structure by reflex.
Order: Bulb Switcher → Total Hamming Distance → Nim Game → X of a Kind in a Deck of Cards → Can Make Arithmetic Progression From Sequence → Construct the Rectangle → Mirror Reflection.
Construct the Rectangle
Core idea: Among all integer pairs
L * W == areawithL >= W, the most square-like one (smallestL - W) is the pair whose two factors hugsqrt(area)from either side. The larger factorLcan never be smaller thansqrt(area)and the smaller factorWcan never be larger than it. So startWatfloor(sqrt(area))and walk it down one step at a time; the firstWthat dividesareaevenly is the closest divisor below the square root, and its partnerL = area // Wis the closest divisor above. That first hit is the answer, so there is no need to keep looking. This costs at mostO(sqrt(area))divisibility checks.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson