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 — O(n²) toggles. 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.

flowchart TD A["a problem that looks like a simulation"] --> B{"what is the structure?"} B -->|"toggled once per divisor"| C["divisors pair up
→ squares are odd → sqrt(n)"] B -->|"sum over all pairs"| D["count per bit position
→ ones x zeros"] B -->|"two players, optimal play"| E["find the losing positions
→ multiples of 4"] B -->|"can these be grouped?"| F["GCD of the frequencies > 1"]

💡 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 — shrinking the pile by exactly four each round until you face zero. The whole solution is return n % 4 != 0, and the reasoning takes longer to say than the code takes to write.

🔓 The 6 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line 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 the problem is not asking you 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²), and 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

bit 0:  0, 0, 0        ones = 0  → 0 x 3 = 0
bit 1:  0, 1, 1        ones = 2  → 2 x 1 = 2
bit 2:  1, 1, 0        ones = 2  → 2 x 1 = 2
bit 3:  0, 1, 0        ones = 1  → 1 x 2 = 2
                                     total = 6

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

Bit-level analytics. Population counts and pairwise-difference totals over large datasets are computed per position, never per pair.
Error-correcting codes. Hamming distance is the foundational metric for code design.
Game AI. Losing-position analysis decides optimal play in combinatorial games.
Inventory and packing. GCD-based grouping determines whether items divide evenly into equal batches.
Layout. Finding the most square rectangle for a given area is a real UI and packing problem.

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.

▶ 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. Target: O(n log n) time.

▶ 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.

7. Common pitfalls 🚫

Simulating the bulbs. O(n²) 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 the stated constraints, 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.
Sorting is not optional for the arithmetic-progression check; the input is explicitly unordered.
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.

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.
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.

Intermediate