Alice and Bob are playing a game where they take turns removing stones from a pile, with Alice going first.
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:
Example 2:
Input: n = 1
Output: false
Explanation:
Constraints:
1 <= n <= 50Problem Overview: You start with n stones. Players remove stones in a fixed decreasing order: 10, 9, 8, ... down to 1. Alice moves first. On each turn the player must remove exactly the required number of stones for that step. If the remaining stones are fewer than the required removal, that player loses. The task is to determine whether Alice wins assuming both players follow the rules.
Approach 1: Strategic Removal Pattern (O(1) time, O(1) space)
The removals follow a deterministic sequence from 10 → 1. Because the move size is predetermined, the game effectively becomes a short simulation. Start with required = 10 and alternate turns between Alice and Bob while subtracting the required value from n. If at any step n < required, the current player cannot make the move and loses immediately. Since there are at most 10 moves in the sequence, the simulation runs in constant time. This approach fits well with problems involving simple rule-based state transitions often seen in simulation or math problems.
Approach 2: Backward Induction Strategy (O(1) time, O(1) space)
You can also reason about the game using classic impartial game analysis. Instead of simulating forward, determine which states are winning or losing by analyzing the final moves. If a player reaches a state where the next required removal is larger than the remaining stones, that state is losing. Working backward through the removal sequence reveals which earlier states force a win for the current player. This technique mirrors the reasoning used in many small deterministic games and connects closely to ideas from game theory and mathematical reasoning. For this specific problem the state space is tiny, so the analysis simplifies to checking whether Alice can legally perform the first few removals before the sequence breaks.
Recommended for interviews: The strategic simulation is what most interviewers expect. It directly mirrors the problem statement and demonstrates clean reasoning about turn-based rules. Backward induction is useful if you want to explain the game-theory perspective and prove why the outcome is deterministic. Showing the quick simulation first confirms understanding, while discussing the backward reasoning highlights deeper problem-solving skill.
The goal is to simulate the game up to the maximum constraint (n <= 50) and determine each possible state where Alice wins or loses. The pattern of stone removal can be observed and used to directly determine if Alice can win given the value of n. Specifically, you can track each turn and adjust the number of stones each player is supposed to remove based on decreasing by 1 each turn. This simulation allows us to record outcomes for each n from 1 to 50 only once.
This C solution uses a dynamic programming approach. It creates a boolean array dp of size 51 to store whether Alice wins at each state (number of stones left). Initially, dp[0] is set to false, meaning with 0 stones Alice loses. For each i from 1 to n, it simulates the removal of stones from 10 down to 1 for Alice. If an opponent leaves a state that leads them to lose, Alice wins that state.
Time Complexity: O(n) due to the simulation of each possible state up to n.
Space Complexity: O(n) for storage of dp array.
Using a backward strategy, Alice can analyze the win/lose states based on backward induction. The key is identifying the last possible winning move working through possible outcomes from the maximum constraint back to 0. This approach can optimize and quickly decide if Alice has a winning move without simulating every possible state.
This C function uses backward induction by exploiting modulo properties to classify outcomes quickly. If n % 11 results in 0 or any number >= 2, it is a winning position for Alice.
Time Complexity: O(1), constant-time evaluation.
Space Complexity: O(1), no additional space usage.
We simulate the game process according to the problem description until the game can no longer continue.
Specifically, we maintain two variables x and k, representing the current number of stones that can be removed and the number of operations performed, respectively. Initially, x = 10 and k = 0.
In each round of operations, if the current number of stones that can be removed x does not exceed the remaining number of stones n, we remove x stones, decrease x by 1, and increase k by 1. Otherwise, we cannot perform the operation, and the game ends.
Finally, we check the parity of k. If k is odd, Alice wins the game; otherwise, Bob wins the game.
The time complexity is O(\sqrt{n}), where n is the number of stones. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Strategic Removal Pattern | Time Complexity: O(n) due to the simulation of each possible state up to n. |
| Backward Induction Strategy | Time Complexity: O(1), constant-time evaluation. |
| Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Strategic Removal Pattern (Direct Simulation) | O(1) | O(1) | Best choice for interviews; directly simulates the fixed removal order from 10 to 1. |
| Backward Induction Strategy | O(1) | O(1) | Useful when explaining the game-theory reasoning and identifying winning or losing states. |
3360. Stone Removal Game #leetcode #javaprogramming #dsa #dsalgo #coding #googleinterview • CodeVia • 160 views views
Watch 3 more video solutions →Practice Stone Removal Game with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor