Watch 4 video solutions for Stone Removal Game, a easy level problem involving Math, Simulation. This walkthrough by CodeVia has 160 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |