#292

Easy

LeetCode Problem Workspace

Nim Game

In Nim Game, determine if you can win given a certain number of stones, assuming optimal play from both players.

Problem Statement

In the Nim Game, you and a friend take turns removing stones from a heap. On each turn, a player can remove 1, 2, or 3 stones from the heap. The player who removes the last stone wins. Given an integer n representing the number of stones in the heap, return true if the first player can win, assuming both players play optimally. Otherwise, return false.

For example, if there are 4 stones, the first player cannot win regardless of their moves, while with 1 or 2 stones, the first player can always win. The solution revolves around determining if n leads to a winning position for the first player. The key lies in recognizing a pattern based on modulo 4.

Examples

Example 1

Input: n = 4

Output: false

These are the possible outcomes:

You remove 1 stone. Your friend removes 3 stones, including the last stone. Your friend wins.
You remove 2 stones. Your friend removes 2 stones, including the last stone. Your friend wins.
You remove 3 stones. Your friend removes the last stone. Your friend wins. In all outcomes, your friend wins.

Example 2

Input: n = 1

Output: true

Example details omitted.

Example 3

Input: n = 2

Output: true

Example details omitted.

Constraints

1 <= n <= 231 - 1

Solution Approach

Mathematical Pattern (Modulo 4)

The solution hinges on recognizing the mathematical pattern based on modulo 4. If n % 4 == 0, then the first player will lose if both play optimally. For any other value of n, the first player has a winning strategy. This pattern forms the core of the solution and allows for an O(1) time complexity.

Game Theory Application

The problem is grounded in game theory, where players alternate moves. By evaluating the possible outcomes, we can conclude that if the number of stones modulo 4 is 0, the first player will eventually be forced into a losing position, given optimal play from both sides.

Optimal Play Analysis

The key to solving this problem lies in understanding that removing stones to a multiple of 4 ensures victory. Players need to think ahead and make moves that leave their opponent with a losing position, thus forcing them to eventually lose the game.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(1) as the solution only requires a single modulo operation. The space complexity is O(1) since no additional space is needed apart from the input variable.

What Interviewers Usually Probe

A correct approach identifies the modulo 4 pattern for optimal play.
The candidate should recognize the game theory basis for the solution.
Candidates who try brute force simulations instead of a mathematical solution may need further guidance.

Common Pitfalls or Variants

Common pitfalls

Overcomplicating the solution by simulating all possible moves instead of using the modulo 4 strategy.
Failing to recognize that the winning and losing positions are based on multiples of 4.
Misunderstanding the alternating nature of the game and assuming a winning strategy when n % 4 == 0.

Follow-up variants

What if players can remove 1, 2, or 3 stones, but the first player can remove up to 4 stones?
How would the game change if there were more than 3 players, all taking turns to remove stones?
What happens if the first player can only remove 1 stone per turn?

FAQ

What is the mathematical pattern in the Nim Game?

The key pattern is based on modulo 4. If the number of stones is divisible by 4, the first player will lose. Otherwise, they can win.

How does game theory apply to the Nim Game?

Game theory helps determine optimal strategies by analyzing possible moves and ensuring that players always end up in a winning position when possible.

What happens if there are 5 stones in the heap?

With 5 stones, the first player can always win by removing 1 stone and leaving 4, which is a losing position for the opponent.

What is the time complexity of the solution?

The time complexity is O(1) since it involves only a single modulo operation.

How can I optimize my solution for the Nim Game?

The most efficient solution is to use the modulo 4 strategy, which guarantees optimal performance in constant time.

terminal

Solution

Solution 1: Finding the Pattern

The first player who gets a multiple of $4$ (i.e., $n$ can be divided by $4$) will lose the game.

1

2

3

class Solution:
    def canWinNim(self, n: int) -> bool:
        return n % 4 != 0

Continue Practicing

#810 chalkboard xor game #1025 divisor game #319 bulb switcher