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 alternately take turns, and you go first.
• On each turn, a player may remove 1 to 3 stones from the heap.
• The one who removes the last stone will be the winner.

Given n, the total number of stones, determine whether you can win the game assuming both you and your friend play optimally. Return true if you can win the game, otherwise, return false.

Clarifying Questions

1. Boundary Conditions:
   • Can n be zero or negative, or should n always be a positive integer?
     • For this problem, it’s assumed that n is a positive integer as specified by the problem constraints in competitive programming platforms.
2. Optimal Play:
   • Both players always play optimally. Do you need to account for any sub-optimal moves?
     • No, both players will always make the best possible moves.

Strategy

The key insight for solving this problem is recognizing the pattern of winning and losing positions:

• If n = 1, 2, or 3, you can take all stones and win.
• If n = 4, no matter how many stones you take (1, 2, or 3), your friend will always be able to take the remaining stones and win. Therefore, n = 4 is a losing position.
• If n = 5, 6, or 7, you can take exactly 1, 2, or 3 stones respectively, leaving your friend with n = 4, a losing position.
• If n = 8, no matter how many stones you take (1, 2, or 3), you will always leave your friend with a position where n = 5, 6, or 7, ensuring they can leave you n = 4.

Therefore, we observe that if n % 4 == 0, you will lose; otherwise, you will win.

Code

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

Time Complexity

The time complexity of this solution is O(1) since the operation of taking the modulus and comparing it to a constant involves a constant amount of work, regardless of the input size.

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?