algoadvance

Leetcode 292. Nim Game

Problem Statement:

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 player can remove 1 to 3 stones.
• The player who removes the last stone wins.

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.

Clarifying Questions:

1. What is the smallest and largest size of the heap n that we can expect?
   • You can assume n is a positive integer, and reasonable constraints would be 1 <= n <= 2^31 - 1.
2. If both players play optimally, does this mean they aim to win if possible?
   • Yes, both players will take their moves in an optimal manner to maximize their own chances of winning.

Strategy:

The problem can be solved using a bit of mathematical insight rather than a complex algorithm.

Observation:

• If there are 1, 2, or 3 stones left, you can remove all stones in your first move and win the game.
• If there are 4 stones left, no matter how many stones you remove (1 to 3), your friend will always be able to remove the remaining stones and win.

From this basis, you can observe the following pattern:

• If n % 4 == 0, you will lose because no matter how you play, the number of stones you leave for your friend is a multiple of 4, leading to a losing position.
• Otherwise, if n % 4 != 0, you will win because you can always adjust your play to leave a multiple of 4 stones for your friend, ensuring their loss.

Thus, the solution is simply to check if n is a multiple of 4.

Code:

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

Time Complexity:

• O(1): The operation to check n % 4 and compare it to 0 is done in constant time.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• 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?