Nim Game
EasyPrompt
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: trueExample 3:
Input: n = 2
Output: true
Constraints:
1 <= n <= 231 - 1
Approaches
3 approaches with complexity analysis and trade-offs.
We can solve this problem using recursion by trying all possible moves and checking if any of them leads to a winning position.
Algorithm
- Check base cases:
- If n ≤ 0, return false
- If n ≤ 3, return true
- Recursively check if we can win by trying all possible moves
- Return true if any move leads to a winning position
Walkthrough
In this approach, we use recursion to simulate all possible moves and determine if we can win. For each turn:
-
Base cases:
- If n = 0, return false (no stones left)
- If n = 1, 2, or 3, return true (can take all stones)
-
For each possible move (1, 2, or 3 stones), we:
- Make the move by subtracting stones
- Recursively check if opponent can win with remaining stones
- If opponent can't win, we win
Here's the implementation:
public boolean canWinNim(int n) { if (n <= 0) return false; if (n <= 3) return true; // Try removing 1, 2, or 3 stones return !(canWinNim(n-1) && canWinNim(n-2) && canWinNim(n-3));}Complexity
Time
O(3^n) - For each position, we make 3 recursive calls
Space
O(n) - Maximum depth of recursion tree
Trade-offs
Pros
Easy to understand and implement
Directly simulates the game process
Works for small inputs
Cons
Extremely inefficient for large inputs
Will cause stack overflow for large n
Many redundant calculations
We can optimize the recursive solution using dynamic programming by storing the results of subproblems to avoid redundant calculations.
Algorithm
- Initialize DP array
- Set base cases (n ≤ 3)
- For each position from 4 to n:
- Check if any move leads to a losing position for opponent
- Return final result
Walkthrough
This approach uses dynamic programming to store intermediate results:
- Create a DP array to store results for each number of stones
- Fill the base cases (n = 1, 2, 3)
- For each position, calculate if it's a winning position based on previous results
Here's the implementation:
public boolean canWinNim(int n) { if (n <= 0) return false; if (n <= 3) return true; boolean[] dp = new boolean[n + 1]; // Base cases dp[1] = dp[2] = dp[3] = true; // Fill DP array for (int i = 4; i <= n; i++) { dp[i] = !(dp[i-1] && dp[i-2] && dp[i-3]); } return dp[n];}Complexity
Time
O(n) - We need to fill the DP array once
Space
O(n) - Size of DP array
Trade-offs
Pros
More efficient than recursive solution
Avoids redundant calculations
Can handle larger inputs than recursive solution
Cons
Still requires O(n) space
Not optimal for very large inputs
May cause memory issues for large n
By analyzing the pattern of winning and losing positions, we can derive a simple mathematical solution.
Algorithm
- Check if n is divisible by 4
- Return true if not divisible by 4, false otherwise
Walkthrough
After analyzing the pattern, we can observe that:
- If n = 1, 2, or 3: You can win by taking all stones
- If n = 4: You will lose no matter what
- If n = 5, 6, or 7: You can win
- If n = 8: You will lose
This forms a pattern where you lose if and only if n is divisible by 4.
Here's the implementation:
public boolean canWinNim(int n) { return n % 4 != 0;}Complexity
Time
O(1) - Just one modulo operation
Space
O(1) - No extra space needed
Trade-offs
Pros
Extremely efficient O(1) solution
No extra space required
Works for all valid inputs
Simple and elegant
Cons
Not intuitive at first glance
Requires understanding of the mathematical pattern
Doesn't show the actual game process
Solutions
Solution
class Solution {public boolean canWinNim(int n) { return n % 4 != 0; }}class Solution {public: bool canWinNim(int n) { return n % 4 != 0; }};class Solution : def canWinNim ( self , n : int ) -> bool : return n % 4 != 0Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.