</> MAANG.io

Intermediate

Intermediate problems that train you to pick the right approach: sliding windows, graphs, dynamic programming and more.

0 of 182 solved 0%

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.

What is the structure of the problem

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 is return 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

Total Hamming Distance worked example

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 n work 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 p and q decide the receptor.

8. Key takeaways

  1. Reason to the answer. Ask what it must be before deciding how to compute it.
  2. Divisors pair, so squares are the exception, the observation behind an entire family of puzzles.
  3. Decompose into independent positions and a quadratic count becomes linear.
  4. Games are decided by losing positions, found by working up from zero.
  5. A GCD answers "can these be grouped evenly?"
  6. Search divisors from the square root when you want the most balanced factor pair.
  7. Unfold reflections into a straight line and the bounces become a parity check.
  8. 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.

Core idea: Whatever you take on your turn (1, 2, or 3 stones), your opponent can take 4 - that and bring the pile down by exactly 4. So multiples of 4 are losing positions for whoever faces them. You go first, so you win exactly when n is not a multiple of 4: return n % 4 != 0. O(1).

Problem, rephrased

You and a friend sit across a table with a single pile of stones between you, playing Nim. On each turn a player must remove 1, 2, or 3 stones (no more, no less), you move first, and whoever removes the last stone wins. You're given the integer n, the number of stones in the starting pile.

Return true if you (the first player) can force a win, and false otherwise. Both players play optimally, so the question is not whether you might win, but whether some strategy of yours wins against perfect play.

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

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.