Nim Game

What they ask

A heap holds n stones. You and the interviewer take turns, and on every turn a player must remove 1, 2 or 3 stones. Whoever removes the last stone wins. You always move first, and both sides play perfectly. Write a function that returns true if you can force a win for a given n.

They usually let you brute-force it first with recursion or a small DP table, then ask you to look at the table and find the pattern.

Examples

• n = 4 returns false: whatever you take (1, 2 or 3), the opponent takes the rest and wins.
• n = 1, n = 2, n = 3 all return true: you just take everything.
• n = 7 returns true: take 3, leave 4, and now the opponent is in the losing position above.

Constraints

• 1 <= n <= 2^31 - 1, so an O(n) table will not pass the largest inputs.

What they look for

• Noticing that every multiple of 4 is a losing position and being able to say why (from any non-multiple of 4 you can always hand the opponent a multiple of 4, and from a multiple of 4 you cannot).
• A one-line O(1) answer after the reasoning, not before it.
• Clean explanation out loud; this was a 30-minute intern round and the interviewer cared more about the argument than the code.