Determine whether the first player can force a win in a take-away game with stones.
Nim Game
You are playing a simple impartial game with one pile of stones.
- There are initially
nstones in the pile. - Two players take turns.
- On each turn, a player must remove 1, 2, or 3 stones from the pile.
- The player who removes the last stone wins.
Assuming both players play optimally, determine whether the first player has a winning strategy.
This is a classic game-theory problem that can often be solved by spotting the losing positions in the game state space.
Input Format
- A single integer
nrepresenting the number of stones in the pile.
Output Format
- Return
trueif the first player can force a win. - Otherwise, return
false.
Constraints
- is within the usual integer range for the platform version of this problem.
- Both players play optimally.
- On each move, a player may remove 1, 2, or 3 stones only.
Example 1
Input
n = 4
Output
false
Explanation
No matter whether the first player removes 1, 2, or 3 stones, the second player can take the remaining stones and win.
Example 2
Input
n = 5
Output
true
Explanation
The first player can remove 1 stone, leaving 4 stones for the opponent, which is a losing position.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.