Stone Removal Game

Easy

#2985Time: 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`.

Patterns

Math

Prompt

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 fewer stone than 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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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:

Alice's Turn: stonesToRemove = 10. Since 12 >= 10, Alice removes 10 stones. Remaining stones: 2. Next player (Bob) must remove 9.
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.

1class Solution {2    public boolean stoneGame(int n) {3        int stones = n;4        int stonesToRemove = 10;5        boolean isAliceTurn = true;6 7        while (stonesToRemove > 0) {8            if (stones < stonesToRemove) {9                // The current player cannot make the move and loses.10                // The winner is the other player.11                return !isAliceTurn;12            }13            14            // The current player makes the move.15            stones -= stonesToRemove;16            17            // Prepare for the next turn.18            stonesToRemove--;19            isAliceTurn = !isAliceTurn;20        }21        22        // The loop finished, meaning stonesToRemove is 0.23        // The player whose turn it is now (isAliceTurn) cannot move and loses.24        // The winner is the player who just moved.25        return !isAliceTurn;26    }27}

Complexity

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`.

Trade-offs

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.

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.

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.

Walkthrough

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.

1class Solution {2    public boolean stoneGame(int n) {3        // Turn 1 (Alice): Loses if n < 10.4        if (n < 10) return false;5        // Turn 2 (Bob): Loses if 10 <= n < 19. Alice wins.6        if (n < 19) return true;7        // Turn 3 (Alice): Loses if 19 <= n < 27.8        if (n < 27) return false;9        // Turn 4 (Bob): Loses if 27 <= n < 34. Alice wins.10        if (n < 34) return true;11        // Turn 5 (Alice): Loses if 34 <= n < 40.12        if (n < 40) return false;13        // Turn 6 (Bob): Loses if 40 <= n < 45. Alice wins.14        if (n < 45) return true;15        // Turn 7 (Alice): Loses if 45 <= n < 49.16        if (n < 49) return false;17        // Turn 8 (Bob): Loses if 49 <= n < 52. Alice wins.18        // Since n <= 50, this covers n=49 and n=50.19        return true;20    }21}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  boolean canAliceWin(int n) {4    int x = 10, k = 0;5    while (n >= x) {6      n -= x;7      --x;8      ++k;9    }10    return k % 2 == 1;11  }12}

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

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem