Watch 10 video solutions for Nim Game, a easy level problem involving Math, Brainteaser, Game Theory. This walkthrough by tecmath has 113,953 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are playing the following Nim Game with your friend:
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 <= 231 - 1Problem Overview: You are given n stones. Two players take turns removing 1 to 3 stones, and whoever removes the last stone wins. Both players play optimally. Your task is to determine whether the first player can guarantee a win.
Approach 1: Dynamic Programming (O(n) time, O(n) space)
This approach models the game using dynamic programming. Define dp[i] as whether the current player can win when i stones remain. A player wins if they can remove 1, 2, or 3 stones and leave the opponent in a losing state. The transition becomes dp[i] = !(dp[i-1] && dp[i-2] && dp[i-3]). If all three next states are winning for the opponent, the current state is losing; otherwise it is winning.
Initialize the base cases: dp[1] = true, dp[2] = true, and dp[3] = true because the first player can take all stones immediately. Iteratively compute values up to n. This approach demonstrates the reasoning behind optimal play and is useful for understanding how small game states propagate to larger ones.
Approach 2: Observation-Based Mathematical Approach (O(1) time, O(1) space)
Looking at the DP pattern reveals a repeating cycle. Positions with n % 4 == 0 are losing states. If there are 4 stones, every move (taking 1–3) leaves the opponent with 3, 2, or 1 stones, all winning states for them. The same logic extends to 8, 12, 16, and so on. Any multiple of 4 forces the current player into a losing position if the opponent plays optimally.
If n % 4 != 0, the first player can always remove n % 4 stones to leave exactly a multiple of 4. From that point on, whatever the opponent removes (1–3), you remove the remaining amount to complete 4. This invariant guarantees that you take the last stone. The reasoning relies on simple modular arithmetic from math and classic game theory principles.
Recommended for interviews: Start by explaining the dynamic programming reasoning to show you understand the state transitions. Then present the mathematical observation that reduces the solution to checking n % 4. Interviewers expect the constant-time solution because it demonstrates pattern recognition and game theory insight.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming | O(n) | O(n) | When deriving the game logic step by step or demonstrating reasoning in interviews |
| Observation-Based Mathematical Rule | O(1) | O(1) | Optimal solution once the repeating pattern (n % 4) is identified |