Nim Game (LeetCode #292)
Nim Game - Video Solution
Watch 10 video solutions for Nim Game, a easy level problem involving Math, Brainteaser, Game Theory. This walkthrough by Programmer Mitch has 13,096 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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: true
Example 3:
Input: n = 2 Output: true
Constraints:
1 <= n <= 231 - 1
Approach Overview
Problem 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.
Complexity Analysis
| 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 |