algoadvance

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, a player may remove 1 to 3 stones from the heap.
The player who removes the last stone is the winner.

Given an integer n, representing 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.

Clarifying Questions:

Is n always a positive integer?
- Yes, it’s guaranteed that n is a positive integer.
Can n be extremely large?
- The value of n can be large, but the solution should efficiently handle it.

Strategy:

The main insight is to recognize the pattern of winning or losing based on the number of stones:

If n is 1, 2, or 3, you can take all the stones and win.
If n is 4, no matter how many stones (1, 2, or 3) you take, your opponent will always be left with a winning position (1, 2, or 3 stones).
Therefore, for n = 4, you will always lose if both play optimally.

When n > 4, you can observe the following pattern repeating:

n % 4 == 0 leads to a losing position as any move leaves your opponent in a winning position.
If you are not facing a multiple of 4, you can always make a move that brings the remaining stones to a multiple of 4 for your opponent, ensuring their loss and your win.

Based on this, the solution can be derived as:

Return true if n % 4 != 0, otherwise false.

Code:

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

Time Complexity:

The time complexity of this solution is (O(1)) since the modulo operation and comparison both take constant time.

By leveraging the nature of divisibility and modular arithmetic, we can determine the winning or losing position for any number of stones in constant time.

Try our interview co-pilot at AlgoAdvance.com

Got blindsided by a question you didn’t expect?
Spend too much time studying?
Or simply don’t have the time to go over all 3000 questions?