LeetCode #292 Nim Game Solution & Explanation

LeetCode Problem

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 person whose turn it is will remove 1 to 3 stones from the heap.
• The one who removes the last stone is the winner.

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.

Example 1:

Input: n = 4
Output: false
Explanation: These are the possible outcomes:
1. You remove 1 stone. Your friend removes 3 stones, including the last stone. Your friend wins.
2. You remove 2 stones. Your friend removes 2 stones, including the last stone. Your friend wins.
3. You remove 3 stones. Your friend removes the last stone. Your friend wins.
In all outcomes, your friend wins.

Example 2:

Input: n = 1
Output: true

Example 3:

Input: n = 2
Output: true

Constraints:

• 1 <= n <= 2³¹ – 1

Solution

This problem boils down to a mathematical concept, which can be resolved by leveraging certain mathematical rules. If the number of stones in the heap, denoted by n, is a multiple of 4, then regardless of your strategy, your friend can always remove a suitable number of stones in each turn, leaving you with 4 stones at the end. In this scenario, no matter how many stones you take, your friend will be able to win. Hence, if n is a multiple of 4, you won’t be able to win.

For instance:

If you take 1 stone, your friend will take 3 stones.
If you take 2 stones, your friend will take 2 stones.
If you take 3 stones, your friend will take 1 stone.

Since you take the first move, your friend can correspondingly maintain a multiple of 4 to ensure they win.

This strategy ensures that your friend can always maintain a multiple of 4 stones, making it impossible for you to win if n is divisible by 4.

C# Solution

Solution1

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

Java Solution

Solution1

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

Conclusion

🧡If my solution helps, that is my honor!

🧡You can support me by sharing my posts, thanks a lot

✅If you got any problem about the explanation, please feel free to let me know

The problem link : Nim Game – LeetCode

Some Random LeetCode posts