Stone Removal Game solution and explanation
3 more videos on this problem
3360. Stone Removal Game #leetcode #javaprogramming #dsa #dsalgo #coding #googleinterviewCodeVia · 3:20 · 164 views
3360. Stone Removal Game (Leetcode Easy)Programming Live with Larry · 3:41 · 155 views
LEETCODE BIWEEKLY CONTEST 144 LEETCODE 3360 EXPLANATIONR Sai Siddhu · 2:49 · 120 views
Leetcode 3360 Stone Removal GameAlgorithmicIQ · 8:07 · 27 views
The 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 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.
def aliceWins(n):
dp = [False] * (n + 1)
for i in range(1, n + 1):
for x in range(10, 0, -1):
if i >= x and not dp[i - x]:
dp[i] = True
break
return dp[n]public class Solution {
public boolean aliceWins(int n) {
boolean[] dp = new boolean[n + 1];
for (int i = 1; i <= n; i++) {
for (int x = 10; x >= 1; x--) {
if (i >= x && !dp[i - x]) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
}#include <vector>
using namespace std;
class Solution {
public:
bool aliceWins(int n) {
vector<bool> dp(n + 1, false);
for (int i = 1; i <= n; ++i) {
for (int x = 10; x >= 1 && x <= i; --x) {
if (!dp[i - x]) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
};function aliceWins(n) {
const dp = new Array(n + 1).fill(false);
for (let i = 1; i <= n; i++) {
for (let x = 10; x >= 1; x--) {
if (i >= x && !dp[i - x]) {
dp[i] = true;
break;
}
}
}
return dp[n];
}#include <stdbool.h>
bool aliceWins(int n) {
bool dp[51] = {false};
dp[0] = false;
for (int i = 1; i <= n; ++i) {
for (int x = 10; x >= 1; --x) {
if (i >= x && !dp[i - x]) {
dp[i] = true;
break;
}
}
}
return dp[n];
}public class Solution {
public bool AliceWins(int n) {
bool[] dp = new bool[n + 1];
for (int i = 1; i <= n; i++) {
for (int x = 10; x >= 1; x--) {
if (i >= x && !dp[i - x]) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
}This Python solution dynamically programs winning moves for Alice by checking all possible stone removals from 10 to 1 and updating the dp array that keeps track of win/lose states.
Time Complexity: O(n) because it iterates from 1 to n.
Space Complexity: O(n) due to the dp list storage.
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.
def aliceWinsBackward(n):
return (n % 11) >= 2 or (n % 11) == 0public class Solution {
public boolean aliceWinsBackward(int n) {
return (n % 11) >= 2 || (n % 11) == 0;
}
}#include <cmath>
using namespace std;
class Solution {
public:
bool aliceWinsBackward(int n) {
return (n % 11) >= 2 || (n % 11) == 0;
}
};function aliceWinsBackward(n) {
return (n % 11) >= 2 || (n % 11) === 0;
}#include <stdbool.h>
bool aliceWinsBackward(int n) {
if (n < 10) return false;
n = (n % 11);
if (n == 0 || n >= 2) {
return true;
}
return false;
}public class Solution {
public bool AliceWinsBackward(int n) {
return (n % 11) >= 2 || (n % 11) == 0;
}
}The Python function leverages the logic where only specific modulo conditions enable Alice's victory, thus enabling a swift win/lose prediction.
Time Complexity: O(1), directly checks the modulo condition.
Space Complexity: O(1), requires no supplementary space.
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).
function canAliceWin(n: number): boolean {
let [x, k] = [10, 0];
while (n >= x) {
n -= x;
--x;
++k;
}
return k % 2 === 1;
}func canAliceWin(n int) bool {
x, k := 10, 0
for n >= x {
n -= x
x--
k++
}
return k%2 == 1
}Complexity comparison
| Approach | Complexity |
|---|---|
| Strategic Removal Pattern | Time Complexity: O(n) because it iterates from 1 to n. |
| Backward Induction Strategy | Time Complexity: O(1), directly checks the modulo condition. |
| Simulation | – |
Complexity analysis
| 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. |
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.