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 - 1The Nim Game is a classic game theory problem where two players take turns removing 1–3 stones from a pile. The goal is to determine whether the first player can guarantee a win assuming both players play optimally.
A good strategy is to start by analyzing small values of n and identifying which positions are winning or losing states. By observing patterns in these outcomes, you’ll notice that certain numbers of stones consistently lead to a losing position if the opponent plays perfectly. This reveals a repeating mathematical pattern that can be checked using a simple modulo observation.
Instead of simulating every move or using recursion, the optimal solution relies on recognizing this mathematical property. Once the pattern is known, the result can be determined in constant time with no additional memory. This makes the solution extremely efficient compared to brute-force or dynamic programming approaches.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Mathematical Pattern (Modulo Observation) | O(1) | O(1) |
| Brute Force / Recursive Game Simulation | O(n) | O(n) |
tecmath
Use these hints if you're stuck. Try solving on your own first.
If there are 5 stones in the heap, could you figure out a way to remove the stones such that you will always be the winner?
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.
Time Complexity: O(1).
Space Complexity: O(1).
1public class Solution {
2 public boolean canWinNim(int n) {
3 return n % 4 != 0;
4 }
5}The Java code follows the same logic using the modulo operator to check if the number of stones is not a multiple of 4.
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.
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.
1Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Nim Game is a well-known introductory game theory problem that sometimes appears in coding interviews. It tests a candidate’s ability to recognize patterns and derive mathematical insights rather than relying solely on brute-force coding.
The optimal approach relies on identifying a repeating mathematical pattern in the number of stones. By analyzing small cases, you can determine which positions are winning or losing and use a simple modulo check to decide if the first player can win.
No special data structure is required for the optimal solution. The problem can be solved using a simple mathematical observation, so only a constant amount of space is needed.
Nim Game involves two players making optimal decisions in turns, where each move affects the opponent’s possible outcomes. Game theory helps determine winning and losing states based on optimal strategies from both players.
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.