Skip to main content
Talentd

Stone Removal Game - Solution & Explanation

EasyMathSimulation13 min read
Practice this problem

Problem Statement

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

Approach Overview

Problem 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 1: Strategic Removal Pattern

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) due to the simulation of each possible state up to n.
Space Complexity: O(n) for storage of dp array.

Try this approach in the editor →

Approach 2: Backward Induction Strategy

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(1), constant-time evaluation.
Space Complexity: O(1), no additional space usage.

Try this approach in the editor →

Approach 3: Simulation

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

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Strategic Removal Pattern

Time Complexity: O(n) due to the simulation of each possible state up to n.
Space Complexity: O(n) for storage of dp array.

Backward Induction Strategy

Time Complexity: O(1), constant-time evaluation.
Space Complexity: O(1), no additional space usage.

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 StrategyO(1)O(1)Useful when explaining the game-theory reasoning and identifying winning or losing states.

Video Solution

3360. Stone Removal Game #leetcode #javaprogramming #dsa #dsalgo #coding #googleinterview • CodeVia • 164 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Stone Removal Game easy or hard?
Stone Removal Game is categorized as an Easy problem. The logic mainly involves following the predefined removal sequence and checking whether the remaining stones allow the next move. Understanding the turn order and edge cases is usually enough to implement the solution quickly.
Stone Removal Game Python/Java solution
The solution translates directly across languages such as Python, Java, C++, C#, C, and JavaScript. Each implementation performs the same constant-time loop that subtracts values from 10 down to 1 while alternating the current player.
How to solve Stone Removal Game in O(1)?
Use a small simulation that subtracts the required number of stones starting from 10 and decreasing each turn. Alternate turns between Alice and Bob while updating the remaining stones. If the remaining stones become smaller than the next required removal, the current player loses. Because the sequence length is constant, the runtime is O(1).
What is the best approach for Stone Removal Game?
The most practical approach is a direct simulation of the required removal sequence from 10 down to 1. Track the remaining stones and alternate turns between Alice and Bob. If the remaining stones are less than the required removal on a player's turn, that player loses. The simulation runs in constant time because the sequence has at most 10 steps.
Is Stone Removal Game asked at Google/Amazon/Meta?
Stone Removal Game represents the type of small deterministic game logic commonly asked in coding interviews at companies like Amazon and Google. Interviewers often use similar problems to test reasoning about turn-based simulations, edge cases, and simple game theory.
What data structure is used in Stone Removal Game?
No complex data structures are required. The solution uses simple integer variables to track the remaining stones, the current removal requirement, and whose turn it is. The focus is on mathematical reasoning and simulation rather than data structure manipulation.
What is the time complexity of Stone Removal Game?
The optimal solution runs in O(1) time and O(1) space. The game has a fixed sequence of removals (10 down to 1), so the algorithm performs at most ten iterations regardless of the value of n.

Ready to solve this problem?

Practice Stone Removal Game with our built-in code editor and test cases.

Practice on FleetCode
Previous

Stone Game IV