Nim Game

Easy

Asked by:

84 views

Topics:

Dynamic ProgrammingGreedy AlgorithmsBit Manipulation

You are playing the following Nim Game with your friend:

Initially, there is a heap of stones on the table.
You and your friend will alternate taking turns, and you go first.
On each turn, the person whose turn it is will remove 1 to 3 stones from the heap.
The one who removes the last stone is the winner.

Given n, the number of stones in the heap, return true if you can win the game assuming both you and your friend play optimally, otherwise return false.

Example 1:

Input: n = 4
Output: false
Explanation: These are the possible outcomes:
1. You remove 1 stone. Your friend removes 3 stones, including the last stone. Your friend wins.
2. You remove 2 stones. Your friend removes 2 stones, including the last stone. Your friend wins.
3. 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 3:

Input: n = 2
Output: true

Constraints:

1 <= n <= 2³¹ - 1

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the possible range for the input integer n, representing the number of stones?
Is 'n' guaranteed to be a non-negative integer?
If n is 0, should I return true or false? (Assuming the first player can't move and loses immediately)
Is there a hard upper limit on the value of n that would cause concern about integer overflow during calculations?
To confirm, both players are playing optimally to win, and the goal is to determine if the first player has a guaranteed win, assuming the second player also plays optimally?

Brute Force Solution

Approach

The Nim Game involves two players taking turns removing stones from a pile. The brute force approach involves exploring every possible combination of moves either player can make until we reach a base case where the winner is determined.

Here's how the algorithm would work step-by-step:

Consider all possible numbers of stones the first player can take on their turn (1, 2, or 3).
For each of those possibilities, consider all possible moves the second player can make in response (again, 1, 2, or 3 stones).
Continue exploring every possible sequence of moves, alternating between player one and player two.
At some point, the pile will be empty. Determine who won based on whose turn it was last.
Repeat this process for every possible starting move for both players.
If player one has a winning strategy in at least one of those possibilities, then player one wins. Otherwise, player two wins.

Code Implementation

def can_win_nim(number_of_stones):
    def can_win(stones_left, is_players_turn):
        if stones_left <= 0:
            #If no stones remain, current player lost.
            return not is_players_turn

        for stones_to_take in range(1, min(4, stones_left + 1)):
            # Trying all possible moves, 1, 2, or 3 stones.
            if not can_win(stones_left - stones_to_take, not is_players_turn):

                return True

        # If no winning move exists, current player loses.
        return False

    # Check if the first player can win the game.
    return can_win(number_of_stones, True)

Big(O) Analysis

Time Complexity

O(4^n) – The brute force approach involves exploring all possible moves in the Nim game. At each turn, a player can remove 1, 2, or 3 stones. This creates a branching factor of 3 or 4 (if the number of stones remaining is greater or equal to 3). With n stones, the depth of the recursion is at most n. Therefore, the total number of possible game states explored grows exponentially. In the worst case, the time complexity approximates O(4^n) due to the branching factor and the depth of the recursion, because we explore all possible combinations of moves.

Space Complexity

O(N) – The described brute force approach inherently involves exploring a decision tree of all possible moves. The depth of this tree is at most N, where N is the number of stones. Since this is a recursive approach, the maximum depth of the recursion stack can be N, leading to O(N) space for the call stack. Therefore, the space complexity is O(N).

Optimal Solution

Approach

The key to winning Nim Game is to realize it's not about how many stones you take, but about leaving your opponent with a specific number. The optimal strategy forces your opponent into a losing position by always making sure the number of remaining stones has a certain property.

Here's how the algorithm would work step-by-step:

Understand that if there are 4 stones left, whoever's turn it is will lose.
Your goal is to always leave your opponent with a number of stones that is a multiple of 4.
On your turn, figure out how many stones you need to take so that the remaining number of stones is divisible by 4.
If the initial number of stones is already divisible by 4, you are guaranteed to lose if your opponent plays optimally.
If the initial number of stones isn't divisible by 4, you can always win by taking the correct number of stones on your first turn to leave a multiple of 4 for your opponent, and then repeat this strategy.

Code Implementation

def can_win_nim(number_of_stones: int) -> bool:
    # If the number of stones is a multiple of 4, you will lose.
    if number_of_stones % 4 == 0:
        return False

    # If not, you can always win by making the number a multiple of 4.
    return True

Big(O) Analysis

Time Complexity

O(1) – The provided strategy involves a single modulo operation (n % 4). This operation takes constant time regardless of the input size 'n'. Therefore, the time complexity of the algorithm is O(1) because the number of operations doesn't scale with the input n.

Space Complexity

O(1) – The algorithm described in the plain English explanation doesn't use any auxiliary data structures like arrays, lists, or hash maps. It only involves checking if the initial number of stones (N) is divisible by 4. Therefore, the algorithm uses a constant amount of extra space, independent of the input size N. This constant space is used for variables to store intermediate calculations (if any were needed, but none are apparent from the provided text) during the divisibility check, so the space complexity is O(1).

Edge Cases

Case	How to Handle
n = 0 (no stones)	The second player wins immediately, so the first player loses; return false.
n = 1, 2, or 3 stones	The first player can remove all stones and win; return true.
n = 4 stones	The first player always loses, no matter how many stones are removed; return false.
Large values of n (e.g., near the maximum integer value)	The pattern (n % 4 == 0 -> false, otherwise true) holds and is computationally inexpensive, ensuring efficiency.
Negative n values (invalid input)	The problem states n is the number of stones, so return false or throw an exception/error for invalid input.
Integer overflow possibility	Since we are only checking `n % 4`, integer overflow is not a concern with standard integer types.
n is the maximum integer value	The n%4 operation will still work correctly without overflow since it is a modulo operation.
No valid solution existing with some initial conditions	This is a deterministic game with an optimal solution for each starting condition, so no 'no solution' case exists.

n = 0 (no stones)

How to Handle:

The second player wins immediately, so the first player loses; return false.

n = 1, 2, or 3 stones

How to Handle:

The first player can remove all stones and win; return true.

n = 4 stones

How to Handle:

The first player always loses, no matter how many stones are removed; return false.

Large values of n (e.g., near the maximum integer value)

How to Handle:

The pattern (n % 4 == 0 -> false, otherwise true) holds and is computationally inexpensive, ensuring efficiency.

Negative n values (invalid input)

How to Handle:

The problem states n is the number of stones, so return false or throw an exception/error for invalid input.

Integer overflow possibility

How to Handle:

Since we are only checking `n % 4`, integer overflow is not a concern with standard integer types.

n is the maximum integer value

How to Handle:

The n%4 operation will still work correctly without overflow since it is a modulo operation.

No valid solution existing with some initial conditions

How to Handle:

This is a deterministic game with an optimal solution for each starting condition, so no 'no solution' case exists.