# Nim Game
**Difficulty:** EASY
[External](https://leetcode.com/problems/nim-game)
Canonical: https://scaleengineer.com/dsa/problems/nim-game
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Game Theory](https://scaleengineer.com/dsa/patterns/game-theory)
---
## Problem
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`

# Approaches
## Recursive Solution
We can solve this problem using recursion by trying all possible moves and checking if any of them leads to a winning position.
**Time:** O(3^n) - For each position, we make 3 recursive calls · **Space:** O(n) - Maximum depth of recursion tree
**Pros:** Easy to understand and implement; Directly simulates the game process; Works for small inputs
**Cons:** Extremely inefficient for large inputs; Will cause stack overflow for large n; Many redundant calculations
### Explanation
In this approach, we use recursion to simulate all possible moves and determine if we can win. For each turn:

1. Base cases: 
   - If n = 0, return false (no stones left)
   - If n = 1, 2, or 3, return true (can take all stones)

2. For each possible move (1, 2, or 3 stones), we:
   - Make the move by subtracting stones
   - Recursively check if opponent can win with remaining stones
   - If opponent can't win, we win

Here's the implementation:

```java
public boolean canWinNim(int n) {
    if (n <= 0) return false;
    if (n <= 3) return true;
    
    // Try removing 1, 2, or 3 stones
    return !(canWinNim(n-1) && canWinNim(n-2) && canWinNim(n-3));
}
```
### Algorithm
1. Check base cases:
   - If n ≤ 0, return false
   - If n ≤ 3, return true
2. Recursively check if we can win by trying all possible moves
3. Return true if any move leads to a winning position

## Dynamic Programming Solution
We can optimize the recursive solution using dynamic programming by storing the results of subproblems to avoid redundant calculations.
**Time:** O(n) - We need to fill the DP array once · **Space:** O(n) - Size of DP array
**Pros:** More efficient than recursive solution; Avoids redundant calculations; Can handle larger inputs than recursive solution
**Cons:** Still requires O(n) space; Not optimal for very large inputs; May cause memory issues for large n
### Explanation
This approach uses dynamic programming to store intermediate results:

1. Create a DP array to store results for each number of stones
2. Fill the base cases (n = 1, 2, 3)
3. For each position, calculate if it's a winning position based on previous results

Here's the implementation:

```java
public boolean canWinNim(int n) {
    if (n <= 0) return false;
    if (n <= 3) return true;
    
    boolean[] dp = new boolean[n + 1];
    // Base cases
    dp[1] = dp[2] = dp[3] = true;
    
    // Fill DP array
    for (int i = 4; i <= n; i++) {
        dp[i] = !(dp[i-1] && dp[i-2] && dp[i-3]);
    }
    
    return dp[n];
}
```
### Algorithm
1. Initialize DP array
2. Set base cases (n ≤ 3)
3. For each position from 4 to n:
   - Check if any move leads to a losing position for opponent
4. Return final result

## Mathematical Pattern Solution
By analyzing the pattern of winning and losing positions, we can derive a simple mathematical solution.
**Time:** O(1) - Just one modulo operation · **Space:** O(1) - No extra space needed
**Pros:** Extremely efficient O(1) solution; No extra space required; Works for all valid inputs; Simple and elegant
**Cons:** Not intuitive at first glance; Requires understanding of the mathematical pattern; Doesn't show the actual game process
### Explanation
After analyzing the pattern, we can observe that:

1. If n = 1, 2, or 3: You can win by taking all stones
2. If n = 4: You will lose no matter what
3. If n = 5, 6, or 7: You can win
4. If n = 8: You will lose

This forms a pattern where you lose if and only if n is divisible by 4.

Here's the implementation:

```java
public boolean canWinNim(int n) {
    return n % 4 != 0;
}
```
### Algorithm
1. Check if n is divisible by 4
2. Return true if not divisible by 4, false otherwise

# Solutions
### Java

```java
class Solution {
public
  boolean canWinNim(int n) { return n % 4 != 0; }
}

```

### CPP

```cpp
class Solution {
public:
  bool canWinNim(int n) { return n % 4 != 0; }
};

```

### Python

```python
class Solution : def canWinNim ( self , n : int ) -> bool : return n % 4 != 0
```