Problem

You are playing a game with your friend where there is a heap of stones on the table. The rules of the game are as follows:

1. You and your friend take turns to remove 1 to 3 stones.
2. The person who removes the last stone is the winner.
3. You have the first turn to remove the stones.

Both you and your friend are very clever and have optimal strategies for the game. You want to determine if you can win the game given the number of stones in the heap.

For example, if there are 4 stones in the heap, then you will not be able to win the game. No matter if you remove 1, 2, or 3 stones, the last stone will always be removed by your friend.

Approach

The strategy to solve this problem revolves around the observation that if the number of stones in the heap is multiple of 4, you will never win the game. This is because no matter how many stones you remove (1, 2 or 3), your friend can always remove enough stones to make the heap size a multiple of 4 again.

For example, if the heap size is 4 (which is a multiple of 4), no matter how many stones you remove in the first turn (1, 2 or 3), your friend can always remove enough stones in their turn to bring the heap size back to zero, thus winning the game.

So, if the initial heap size n is not a multiple of 4, you can always decrease the heap size to a multiple of 4 after your turn, giving you the upper hand and hence the ability to win.

Solution

Python

1
2python
3class Solution:
4    def canWinNim(self, n: int) -> bool:
5        # If the number of stones is not a multiple of 4, you can win
6        return n % 4 != 0

Java

1
2java
3public class Solution {
4    public boolean canWinNim(int n) {
5        // If the number of stones is not a multiple of 4, you can win
6        return n % 4 != 0;
7    }
8}

JavaScript

1
2javascript
3var canWinNim = function(n) {
4    // If the number of stones is not a multiple of 4, you can win
5    return n % 4 !== 0;
6};

C++

1
2cpp
3class Solution {
4public:
5    bool canWinNim(int n) {
6        // If the number of stones is not a multiple of 4, you can win
7        return n % 4 != 0;
8    }
9};

C#

1
2csharp
3public class Solution {
4    public bool CanWinNim(int n) {
5        // If the number of stones is not a multiple of 4, you can win
6        return n % 4 != 0;
7    }
8}

In each of the methods above, we perform a modulus operation on the number of stones n with 4, and return whether the result is not equal to 0, which determines whether you can win the game or not.# Explanation

The solution outlined in each of the code snippets above uses the modulus operator to determine the remainder when the number of stones is divided by 4. If the number of stones in the heap is not a multiple of 4, the modulus operation will return a non-zero value and the method will return true indicating that you can win the game. Conversely, if the number of stones in the heap is a multiple of 4, the modulus operation will return zero and the method will return false indicating that you cannot win the game.

By moving first and using this optimal strategy, you can always make sure that after your move, the number of stones in the heap is a multiple of 4. This will ensure that no matter how many stones your friend removes on their turn, you will always be able to bring the number of stones in the heap back to a multiple of 4 on your next turn, keeping the advantage in your favour.

This strategy makes it impossible for your friend to ever reach a position where they can remove the last stone and win the game, meaning that you will always win the game as long as the initial number of stones in the heap is not a multiple of 4.

Note that while this algorithm is able to solve the problem effectively, it may not necessarily be the most efficient solution for larger inputs due to the computational overhead associated with the modulus operation. However, given the nature of the problem and the constraints imposed on the number of stones, this solution is both practical and easy to understand.