Problem Statement: You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Write a function to determine whether you can win the game given the number of stones in the heap.

Example 1: Input: 4 Output: false Explanation: If there are 4 stones in the heap, then you will never win the game; No matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.

Example 2: Input: 5 Output: true Explanation: If there are 5 stones in the heap, then you can remove 1 stone, and your friend removes the other 3 stones. Then you take the last stone and win the game.

Solution: The game of Nim is a two-player game in which players take turns removing items from a pile. On each turn, a player can remove between 1 and 3 items. The player who removes the last item from the pile wins the game.

This problem can be solved through simple observation. If there is only one stone or two stones in the heap, then obviously the player who starts the game will win because he/she can remove all the stones.

If there are three stones in the heap, then the player who starts the game can remove one stone to reduce it to two, which we have already shown to be a win, or remove two stones to reduce it to one, which again, he/she will win.

If there are four stones in the heap, no matter how many stones the player who starts the game removes (1, 2, or 3), he/she cannot win, as the second player can take remaining stones and win the game.

If there are five stones in the heap, the player who starts the game can remove one stone to reduce it to four stones, which he/she can win as we have shown, or remove two stones to reduce it to three stones, which he/she can also win as we have already seen. Or he/she can remove three stones to reduce it to two stones, which is clearly a win as we have shown. Hence the first player can always win if the number of stones in the heap is not divisible by 4.

Similarly, we can prove that if the number of stones in the heap is divisible by 4, then the first player cannot win the game.

Here is the Python code to implement the above solution:

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

Time Complexity: O(1)

Space Complexity: O(1)

We can see that the time complexity of the above solution is O(1) and the space complexity is also O(1), as we are not using any auxiliary data structure to solve this problem.

1