257. Nim Game
You and a rival play a take-away game over a single pile of n stones. Moves alternate and you go first; on each move a player must remove 1, 2, or 3 stones. Whoever removes the last stone wins.
Both players play perfectly — no blunders, ever. The function receives the integer n and returns a boolean: true if the first player (you) can force a victory no matter how the opponent responds, false if the opponent can always deny you.
Before reaching for code, try tiny piles by hand: with 1, 2, or 3 stones you simply grab everything and win on the spot. With 4 stones, every option you have leaves your rival a pile of 1–3 — an instant win for them.
Example 1:
Input: n = 4
Output: false
Explanation: Taking 1, 2, or 3 stones leaves 3, 2, or 1 for the opponent, who takes them all and wins. Every branch loses, so 4 is a lost position.
Example 2:
Input: n = 1
Output: true
Explanation: One stone, one move: you take it and win immediately.
Constraints:
- 1 ≤ n ≤ 10⁶
Hints:
Work out small piles by hand: 1, 2, 3 are wins and 4 is a loss. Continue to 5, 6, 7, 8 — a pattern with period 4 emerges.
Game DP: a pile is winning exactly when at least one move hands the opponent a *losing* pile, i.e. win[i] = !(win[i−1] && win[i−2] && win[i−3]). Only the last three values are ever needed.
From a multiple of 4, whatever k ∈ {1, 2, 3} you take, the opponent answers with 4 − k and the pile is a multiple of 4 again. That invariant collapses the entire game into one modulo check.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 4
Expected output: false