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.
In this approach, the key observation is that if n is a multiple of 4, you will lose the game if both play optimally. Hence, you can immediately return false in this case. The reason is that no matter what you do (removing 1 to 3 stones), you will leave the opponent with a number of stones that are not a multiple of 4, enabling them to adjust their removal so that you fail.
The code checks the remainder of n divided by 4. If the remainder is not zero, you can win; otherwise, you lose.
C++
Java
Python
C#
JavaScript
Time Complexity: O(1).
Space Complexity: O(1).
A more generalized approach can be a dynamic programming technique to solve the problem for smaller values and build up the solution by using previously solved values. This approach can be used when learning optimal sub-structure is more relevant and the pattern is not known beforehand.
This C solution uses a cyclic buffer to store states and computes dynamically from known base conditions. The buffer size is 4 because we only need the last 3 results to compute the current state.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n).
Space Complexity: O(1) due to constant space usage.
However, it is important to note for large n, this specific approach might be constrained by array size limitations in practice.
| Approach | Complexity |
|---|---|
| Observation-Based Mathematical Approach | Time Complexity: O(1). |
| Dynamic Programming Approach | Time Complexity: O(n). |
| 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 |
The Game of Nim - a math game of strategy using matchsticks! • tecmath • 113,953 views views
Watch 9 more video solutions →Practice Nim Game with our built-in code editor and test cases.
Practice on FleetCode