Difficulty: Easy | Acceptance: 59.80% | Paid: No Topics: Math, Brainteaser, Game Theory
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 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.
- Examples
- Constraints
- Mathematical Approach
- Dynamic Programming Approach
- Recursive with Memoization Approach
Examples
Example 1:
Input: n = 4
Output: false
Explanation: These are the possible outcomes:
1. You remove 1 stone. Your friend removes 3 stones, winning the game.
2. You remove 2 stones. Your friend removes 2 stones, winning the game.
3. You remove 3 stones. Your friend removes the last stone, winning the game.
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
Mathematical Approach
Intuition If the number of stones is a multiple of 4, you will always lose with optimal play from both sides. Otherwise, you can always take enough stones to leave a multiple of 4 for your opponent.
Steps
- Check if n is divisible by 4
- If yes, return false (you lose)
- Otherwise, return true (you win)
class Solution:
def canWinNim(self, n: int) -> bool:
return n % 4 != 0
Complexity
- Time: O(1)
- Space: O(1)
- Notes: This is the optimal solution with constant time and space complexity.
Dynamic Programming Approach
Intuition Build up the solution from base cases. For each number of stones, you win if at least one of your possible moves (taking 1, 2, or 3 stones) leaves your opponent in a losing position.
Steps
- Initialize dp array where dp[i] represents if you can win with i stones
- Set base cases: dp[1] = dp[2] = dp[3] = true
- For each i from 4 to n, dp[i] = !dp[i-1] || !dp[i-2] || !dp[i-3]
- Return dp[n]
class Solution:
def canWinNim(self, n: int) -> bool:
if n <= 3:
return True
dp = [False] * (n + 1)
dp[1] = dp[2] = dp[3] = True
for i in range(4, n + 1):
dp[i] = not dp[i-1] or not dp[i-2] or not dp[i-3]
return dp[n]
Complexity
- Time: O(n)
- Space: O(n)
- Notes: This approach reveals the pattern but is not practical for large n due to memory constraints.
Recursive with Memoization Approach
Intuition Use recursion to explore all possible moves. If any move leads to the opponent losing, you win. Memoization prevents redundant calculations.
Steps
- Create a memoization map/dictionary
- Define recursive function that checks if you can win with given stones
- Base case: if stones <= 3, return true
- Check memo for cached result
- Recursively check all three possible moves
- Cache and return result
class Solution:
def canWinNim(self, n: int) -> bool:
memo = {}
def canWin(stones):
if stones <= 3:
return True
if stones in memo:
return memo[stones]
result = not canWin(stones - 1) or not canWin(stones - 2) or not canWin(stones - 3)
memo[stones] = result
return result
return canWin(n)
Complexity
- Time: O(n)
- Space: O(n)
- Notes: May cause stack overflow for very large n due to recursion depth limits.