Nim Game

Published: Jul 21, 2024

Problem Description

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.

Constraints:

• 1 <= n <= 2**31 - 1

https://leetcode.com/problems/nim-game/

Examples

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

How to Solve

This is a famous Nim Game problem. Two people take turns one by one. In the end, one becomes a winner while an opponent becomes a loser, or vice versa. To solve this type of problems, finding out the condition to win is important. Once the winning condition is identified, the solution can be very simple like this nim game.

In this case, the winning condition of the first person is that the given number is not a multiple of 4. Players can take stones 1, 2, or 3 from the problem description. For the first person to make the opponent to lose, the total number fo stones should not be multiple of 4. That being said, the solution is simple.

Solution

class NimGame {
public:
    bool canWinNim(int n) {
        return n % 4 != 0;
    }
};

class NimGame {
    public boolean canWinNim(int n) {
        return n % 4 != 0;
    }
}

/**
 * @param {number} n
 * @return {boolean}
 */
var canWinNim = function(n) {
    return n % 4 !== 0;
};

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

# @param {Integer} n
# @return {Boolean}
def can_win_nim(n)
    n % 4 != 0
end

Complexities

• Time: O(1)
• Space: O(1)