# Stone Removal Game
**Difficulty:** EASY
[External](https://leetcode.com/problems/stone-removal-game)
Canonical: https://scaleengineer.com/dsa/problems/stone-removal-game
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
---
## Problem
Alice and Bob are playing a game where they take turns removing stones from a pile, with _Alice going first_.

* Alice starts by removing **exactly** 10 stones on her first turn.
* For each subsequent turn, each player removes **exactly** 1 fewerstonethan the previous opponent.

The player who cannot make a move loses the game.

Given a positive integer `n`, return `true` if Alice wins the game and `false` otherwise.

**Example 1:**

**Input:** n = 12

**Output:** true

**Explanation:**

* Alice removes 10 stones on her first turn, leaving 2 stones for Bob.
* Bob cannot remove 9 stones, so Alice wins.

**Example 2:**

**Input:** n = 1

**Output:** false

**Explanation:**

* Alice cannot remove 10 stones, so Alice loses.

**Constraints:**

* `1 <= n <= 50`

# Approaches
## Direct Simulation
This approach directly simulates the game turn by turn as described in the problem. We maintain the state of the game, which includes the number of remaining stones, the number of stones to be removed in the current turn, and whose turn it is. The simulation proceeds until a player is unable to make their required move, at which point that player loses and the game ends.
**Time:** O(1) - The game has a maximum of 10 turns (removing 10, 9, ..., 1 stones). The `while` loop runs at most 10 times, which is a constant number of operations. · **Space:** O(1) - We only use a few variables to store the game's state, which does not depend on the input size `n`.
**Pros:** It is intuitive and directly follows the rules of the game.; The logic is straightforward to implement and debug.; It is very efficient for the given constraints.
**Cons:** While still very efficient (O(1)), it involves a loop, making it slightly slower in practice than a direct mathematical check.
### Explanation
The simulation starts with Alice's turn, where she needs to remove 10 stones. We use a loop to represent the turns of the game. In each turn, we check if the current player has enough stones to make the required move. If not, that player loses, and the other player wins. If the move is possible, we update the number of stones and prepare for the next player's turn by reducing the number of stones to be removed by one.

For example, if `n = 12`:
1.  **Alice's Turn:** `stonesToRemove = 10`. Since `12 >= 10`, Alice removes 10 stones. Remaining stones: `2`. Next player (Bob) must remove `9`.
2.  **Bob's Turn:** `stonesToRemove = 9`. Since `2 < 9`, Bob cannot make the move and loses. Therefore, Alice wins.

The simulation continues until a player loses or all possible moves (from 10 down to 1) are exhausted.

```java
class Solution {
    public boolean stoneGame(int n) {
        int stones = n;
        int stonesToRemove = 10;
        boolean isAliceTurn = true;

        while (stonesToRemove > 0) {
            if (stones < stonesToRemove) {
                // The current player cannot make the move and loses.
                // The winner is the other player.
                return !isAliceTurn;
            }
            
            // The current player makes the move.
            stones -= stonesToRemove;
            
            // Prepare for the next turn.
            stonesToRemove--;
            isAliceTurn = !isAliceTurn;
        }
        
        // The loop finished, meaning stonesToRemove is 0.
        // The player whose turn it is now (isAliceTurn) cannot move and loses.
        // The winner is the player who just moved.
        return !isAliceTurn;
    }
}
```
### Algorithm
- Initialize `stones = n`, `stonesToRemove = 10`, and a boolean `isAliceTurn = true`.
- Start a loop that continues as long as `stonesToRemove` is greater than 0.
- Inside the loop, check if the current player can make a move (`stones >= stonesToRemove`).
- If the player cannot move, they lose. The winner is the other player. Return `!isAliceTurn`.
- If the move is possible, update `stones` by subtracting `stonesToRemove`.
- Prepare for the next turn: decrement `stonesToRemove` and flip `isAliceTurn`.
- If the loop completes, it means `stonesToRemove` reached 0. The player whose turn it is now cannot make a valid move and loses. The winner is the player who made the last move. Return `!isAliceTurn`.

## Mathematical Analysis with Thresholds
Since the game is deterministic (players have no choices on the number of stones to remove), the outcome depends solely on the initial number of stones, `n`. We can analyze the game to find the exact ranges of `n` for which Alice wins or loses. This allows us to solve the problem with a series of simple comparisons, avoiding any loops or recursion.
**Time:** O(1) - The solution involves a fixed number of `if` statements, resulting in constant time execution regardless of the value of `n`. · **Space:** O(1) - No data structures are used, and the memory usage is constant.
**Pros:** Extremely fast, as it performs a constant number of comparisons.; The most efficient solution possible in terms of execution time.; Requires no extra space.
**Cons:** Requires pre-analysis of the game to derive the winning and losing ranges.; The logic might be less immediately obvious compared to a direct simulation.
### Explanation
The core idea is to determine how many stones are needed to survive each turn. The number of stones removed per turn is a fixed sequence: 10, 9, 8, ..., 1.

- To survive Turn 1 (Alice), `n` must be at least 10.
- To survive Turn 2 (Bob), `n` must be at least `10 + 9 = 19`.
- To survive Turn 3 (Alice), `n` must be at least `19 + 8 = 27`.

We can define thresholds based on these cumulative sums:
- If `n < 10`, Alice loses on her first turn.
- If `10 <= n < 19`, Alice moves, but Bob cannot. Alice wins.
- If `19 <= n < 27`, Bob moves, but Alice cannot make her second move. Alice loses.
- This pattern continues. Alice wins if the game ends on an even-numbered turn (Bob's turn).

Given the constraint `n <= 50`, we can implement this with a simple set of conditional checks.

```java
class Solution {
    public boolean stoneGame(int n) {
        // Turn 1 (Alice): Loses if n < 10.
        if (n < 10) return false;
        // Turn 2 (Bob): Loses if 10 <= n < 19. Alice wins.
        if (n < 19) return true;
        // Turn 3 (Alice): Loses if 19 <= n < 27.
        if (n < 27) return false;
        // Turn 4 (Bob): Loses if 27 <= n < 34. Alice wins.
        if (n < 34) return true;
        // Turn 5 (Alice): Loses if 34 <= n < 40.
        if (n < 40) return false;
        // Turn 6 (Bob): Loses if 40 <= n < 45. Alice wins.
        if (n < 45) return true;
        // Turn 7 (Alice): Loses if 45 <= n < 49.
        if (n < 49) return false;
        // Turn 8 (Bob): Loses if 49 <= n < 52. Alice wins.
        // Since n <= 50, this covers n=49 and n=50.
        return true;
    }
}
```
### Algorithm
- Pre-calculate the cumulative number of stones required to survive each turn. Let `C(k)` be the total stones needed to complete `k` turns.
- `C(1) = 10`
- `C(2) = 10 + 9 = 19`
- `C(3) = 19 + 8 = 27`
- ...and so on.
- Determine the winner by checking which range the initial number of stones `n` falls into.
- Alice wins if the game ends on Bob's turn (turn 2, 4, 6, etc.). This corresponds to `C(1) <= n < C(2)`, `C(3) <= n < C(4)`, etc.
- Implement this logic using a series of `if` conditions.

# Solutions
### Java

```java
class Solution {
public
  boolean canAliceWin(int n) {
    int x = 10, k = 0;
    while (n >= x) {
      n -= x;
      --x;
      ++k;
    }
    return k % 2 == 1;
  }
}

```

### CPP

```cpp
class Solution { public: bool canAliceWin ( int n ) { int x = 10 , k = 0 ; while ( n >= x ) { n -= x ; -- x ; ++ k ; } return k % 2 ; } };
```

### Python

```python
class Solution : def canAliceWin ( self , n : int ) -> bool : x , k = 10 , 0 while n >= x : n -= x x -= 1 k += 1 return k % 2 == 1
```