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 in a pile. Two players take turns removing 1 to 3 stones. Whoever removes the last stone wins. Both players play optimally. The task is to determine if the first player can guarantee a win for a given n.
Approach 1: Dynamic Programming (O(n) time, O(n) space)
Start by modeling the game as a sequence of states where dp[i] represents whether the current player can win with i stones remaining. From state i, the player can remove 1, 2, or 3 stones, moving the opponent to i-1, i-2, or i-3. If any of those states is losing for the opponent, then dp[i] is winning. Initialize base cases: dp[1], dp[2], and dp[3] are winning states because the player can take all stones. Iterate from 4 up to n and compute the state based on the previous three values. This approach builds intuition for impartial games and mirrors typical dynamic programming reasoning, but it requires linear space and time.
Approach 2: Observation-Based Mathematical Approach (O(1) time, O(1) space)
Once you list the first few DP states, a pattern emerges: losing positions occur when the number of stones is a multiple of 4. If n = 4, every move (removing 1, 2, or 3 stones) leaves 3, 2, or 1 stones for the opponent—each a winning state for them. The same logic repeats for 8, 12, 16.... When n % 4 == 0, the first player loses because every move gives the opponent a winning configuration. When n % 4 != 0, the first player can remove n % 4 stones to force the opponent into a multiple-of-4 state and maintain that invariant for the rest of the game.
This observation turns the entire problem into a single modulus check: return false if n % 4 == 0, otherwise return true. The reasoning comes from classic game theory analysis combined with simple math. No simulation or recursion is required.
Recommended for interviews: Interviewers expect the mathematical observation. Starting with the DP formulation shows you understand state transitions and optimal play. Recognizing the repeating pattern and reducing the solution to n % 4 demonstrates strong analytical skills and familiarity with classic game-theory problems.
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.
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.
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.
The first player who gets a multiple of 4 (i.e., n can be divided by 4) will lose the game.
Proof:
n \lt 4, the first player can directly take all the stones, so the first player will win the game.n = 4, no matter whether the first player chooses 1, 2, 3, the second player can always choose the remaining number, so the first player will lose the game.4 \lt n \lt 8, i.e., n = 5, 6, 7, the first player can correspondingly reduce the number to 4, then the "death number" 4 is given to the second player, and the second player will lose the game.n = 8, no matter whether the first player chooses 1, 2, 3, it will leave a number between 4 \lt n \lt 8 to the second player, so the first player will lose the game.n, and n can be divided by 4, he will lose the game, otherwise, he will win the game.The time complexity is O(1), and the space complexity is O(1).
| Approach | Complexity |
|---|---|
| Observation-Based Mathematical Approach | Time Complexity: O(1). |
| Dynamic Programming Approach | Time Complexity: O(n). |
| Finding the Pattern | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming | O(n) | O(n) | When deriving the pattern or explaining optimal game state transitions |
| Observation-Based Mathematical Approach | O(1) | O(1) | Best for production or interviews once the n % 4 insight is recognized |
Nim Game (LeetCode #292) • Programmer Mitch • 13,089 views views
Watch 9 more video solutions →Practice Nim Game with our built-in code editor and test cases.
Practice on FleetCode