Nim Game - 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.
Input & Output
Example 1 — Small Winning Position
$
Input:
n = 4
›
Output:
false
💡 Note:
No matter what you choose (1, 2, or 3 stones), your opponent can take the remaining stones and win. If you take 1, opponent can take 3. If you take 2, opponent can take 2. If you take 3, opponent can take 1.
Example 2 — Winning Move Available
$
Input:
n = 1
›
Output:
true
💡 Note:
You can take the last stone directly and win the game.
Example 3 — Strategic Winning
$
Input:
n = 5
›
Output:
true
💡 Note:
You can take 1 stone, leaving 4 stones for your opponent. From 4 stones, your opponent will be in a losing position (any move they make puts you in a winning position).
Constraints
- 1 ≤ n ≤ 2³¹ - 1
Visualization
Tap to expand
Understanding the Visualization
1
Input
Number of stones n
2
Pattern Check
Check if n is divisible by 4
3
Result
Return true if n % 4 != 0, false otherwise
Key Takeaway
🎯 Key Insight: If n is divisible by 4, you're in a losing position; otherwise, you can always win by leaving your opponent with a multiple of 4
💡
Explanation
AI Ready
💡 Suggestion
Tab
to accept
Esc
to dismiss
// Output will appear here after running code