Alice and Bob continue their games with stones. There is a row of n stones, and each stone has an associated value. You are given an integer array stones, where stones[i] is the value of the ith stone.
Alice and Bob take turns, with Alice starting first. On each turn, the player may remove any stone from stones. The player who removes a stone loses if the sum of the values of all removed stones is divisible by 3. Bob will win automatically if there are no remaining stones (even if it is Alice's turn).
Assuming both players play optimally, return true if Alice wins and false if Bob wins.
Example 1:
Input: stones = [2,1] Output: true Explanation: The game will be played as follows: - Turn 1: Alice can remove either stone. - Turn 2: Bob removes the remaining stone. The sum of the removed stones is 1 + 2 = 3 and is divisible by 3. Therefore, Bob loses and Alice wins the game.
Example 2:
Input: stones = [2] Output: false Explanation: Alice will remove the only stone, and the sum of the values on the removed stones is 2. Since all the stones are removed and the sum of values is not divisible by 3, Bob wins the game.
Example 3:
Input: stones = [5,1,2,4,3] Output: false Explanation: Bob will always win. One possible way for Bob to win is shown below: - Turn 1: Alice can remove the second stone with value 1. Sum of removed stones = 1. - Turn 2: Bob removes the fifth stone with value 3. Sum of removed stones = 1 + 3 = 4. - Turn 3: Alices removes the fourth stone with value 4. Sum of removed stones = 1 + 3 + 4 = 8. - Turn 4: Bob removes the third stone with value 2. Sum of removed stones = 1 + 3 + 4 + 2 = 10. - Turn 5: Alice removes the first stone with value 5. Sum of removed stones = 1 + 3 + 4 + 2 + 5 = 15. Alice loses the game because the sum of the removed stones (15) is divisible by 3. Bob wins the game.
Constraints:
1 <= stones.length <= 1051 <= stones[i] <= 104Problem Overview: You are given an array of stones where each value contributes to a running sum. Players alternately remove a stone, and if the total sum becomes divisible by 3, the player who made that move loses. Alice starts first. The goal is to determine whether Alice can guarantee a win assuming both players play optimally.
Approach 1: Simulated Play with Greedy Heuristic (O(n) time, O(1) space)
The game depends only on the remainder of each stone modulo 3. First count how many stones produce remainders 0, 1, and 2. During simulation, players avoid moves that make the running sum divisible by 3. Greedy selection prefers stones that keep the sum in a safe state while forcing the opponent into a losing move. Stones with remainder 0 do not change the sum modulo but flip the turn pressure, which creates alternating traps. By simulating decisions using the counts of each remainder group, you approximate optimal play without exploring every game branch.
Approach 2: Modulo Counting Strategy (O(n) time, O(1) space)
The key insight is that only the remainder of each stone modulo 3 matters. Compute counts c0, c1, and c2 where stone % 3 equals 0, 1, or 2. Stones with remainder 0 keep the sum unchanged but swap the advantage between players. The outcome depends on how many remainder-1 and remainder-2 stones exist relative to each other. If c0 is even, Alice wins only when both c1 and c2 are non‑zero. If c0 is odd, the difference between c1 and c2 must exceed 2 for Alice to win. This reasoning collapses the entire game tree into a few arithmetic conditions derived from remainder counts.
The solution relies heavily on counting frequencies and understanding the modular behavior of the running sum. The decision logic is essentially a compact form of game theory, where each move attempts to push the opponent into a forced losing state. The input itself is processed using a simple array traversal.
Recommended for interviews: The modulo counting strategy is what interviewers expect. It demonstrates that you recognized the invariant created by sum % 3 and reduced the entire game to three counters and a few conditional checks. Explaining the greedy simulation first can show understanding of the gameplay mechanics, but the counting approach proves you can compress a game-theory problem into an O(n) pass with constant space.
In this approach, the key is to utilize modulo 3 operations, as the sum's divisibility by 3 determines the game outcome. Count the stones of type 0, 1, and 2 based on their values modulo 3. Our strategy revolves around these types to determine the moves for both players. Simply analyzing number parity and the effect of moves will help us conclude the result in constant time complexity.
Here, we count the stones of each type (0, 1, 2). The decision tree splits based on the count of type 0. If even, Alice can potentially make Bob lose by considering counts of types 1 and 2. If odd, the difference in counts of types 1 and 2 helps decide if Alice can manipulate the game optimally.
Time Complexity: O(n) since we traverse the array once to count the stones types. Space Complexity: O(1) since the extra storage is negligible.
This approach considers playing out a few scenarios following a simulated game sequence. Instead of brute forcing all possibilities, we use a greedy heuristic on types 1 and 2 to evaluate the game's progress. This approach is less efficient in space usage but can illuminate tactical strengths in specific board states.
Utilizing a smarter count approach, this solution effectively tries to simulate a few optimal moves before deciding based on the heuristics of count divergence and parity.
Time Complexity: O(n). Space Complexity: O(1).
Since the player's goal is to ensure the total value of the removed stones is not divisible by 3, we only need to consider the remainder of each stone's value when divided by 3.
We use an array cnt of length 3 to maintain the count of the current remaining stones' values modulo 3, where cnt[0] represents the count of stones with a remainder of 0, and cnt[1] and cnt[2] respectively represent the counts of stones with remainders of 1 and 2.
In the first round, Alice cannot remove stones with a remainder of 0, as this would make the total value of the removed stones divisible by 3. Therefore, Alice can only remove stones with a remainder of 1 or 2.
First, let's consider the case where Alice removes a stone with a remainder of 1. If Alice removes a stone with a remainder of 1, the remainder of the total value of stones 0 against 3 will not change, so stones with a value remainder of 0 can be removed in any round, which we will not consider for now. Thus, Bob can only remove stones with a remainder of 1, followed by Alice removing stones with a remainder of 2, and so on, in the sequence 1, 1, 2, 1, 2, ldots. In this scenario, if the final round is odd and there are still remaining stones, then Alice wins; otherwise, Bob wins.
For the case where Alice removes a stone with a remainder of 2 in the first round, we can draw a similar conclusion.
The time complexity is O(n), where n is the length of the array stones. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
JavaScript
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Modulo Counting Strategy | Time Complexity: O(n) since we traverse the array once to count the stones types. Space Complexity: O(1) since the extra storage is negligible. |
| Simulated Play with Greedy Heuristic | Time Complexity: O(n). Space Complexity: O(1). |
| Greedy + Case Discussion | — |
| Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulated Play with Greedy Heuristic | O(n) | O(1) | Useful to reason about gameplay mechanics and understand how moves affect the running sum modulo 3. |
| Modulo Counting Strategy | O(n) | O(1) | Best approach for interviews and production solutions. Converts the game into simple remainder counts and deterministic conditions. |
2029. Stone Game IX (Leetcode Medium) • Programming Live with Larry • 1,581 views views
Watch 4 more video solutions →Practice Stone Game IX with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor