Solution: Nim Game

Statement▼

You and a friend are playing a game called the Nim Game with a heap of stones. The rules are as follows:

There is a single heap containing n stones.
You and your friend take alternating turns, with you going first.
On each turn, the current player must remove between $1$ and $3$ stones (inclusive) from the heap.
The player who removes the last stone wins the game.

Given n, the number of stones in the heap, return TRUE if you can win the game assuming both players play optimally, otherwise return FALSE.

Constraints:

$1 \leq$ n $\leq 2^{31} - 1$

The key insight behind this problem lies in a simple mathematical pattern from game theory. As each player can remove $1$ , $2$ , or $3$ stones per turn, the critical observation is that if the number of stones n is a multiple of ...

⋮

Tap here to switch tabs

Problem

Submissions

Solution

Home

Courses

Grokking the Coding Interview Patterns

Solution: Nim Game

Statement▼

You and a friend are playing a game called the Nim Game with a heap of stones. The rules are as follows:

There is a single heap containing n stones.
You and your friend take alternating turns, with you going first.
On each turn, the current player must remove between $1$ and $3$ stones (inclusive) from the heap.
The player who removes the last stone wins the game.

Given n, the number of stones in the heap, return TRUE if you can win the game assuming both players play optimally, otherwise return FALSE.

Constraints:

$1 \leq$ n $\leq 2^{31} - 1$