Watch 5 video solutions for Stone Game IX, a medium level problem involving Array, Math, Greedy. This walkthrough by Programming Live with Larry has 1,581 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |