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] <= 104Stone Game IX is a game theory problem where players remove stones and must avoid making the total sum divisible by 3. The key observation is that only the remainder of each stone modulo 3 affects the outcome. Instead of tracking the full sum, we count how many stones fall into the groups 0, 1, and 2.
Using these counts, the game can be reasoned about with a greedy and parity-based strategy. Stones with remainder 0 mainly influence turn switching, while stones with remainders 1 and 2 determine whether players can keep the running sum away from multiples of 3. By analyzing how these counts interact and which player is forced into a losing move, we can determine if the first player (Alice) can guarantee a win.
The solution involves a single pass to count remainders and then applying game rules derived from these counts. This leads to an efficient approach with O(n) time complexity and O(1) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Counting remainders with greedy game analysis | O(n) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
There are limited outcomes given the current sum and the stones remaining.
Can we greedily simulate starting with taking a stone with remainder 1 or 2 divided by 3?
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The losing condition occurs when the running sum becomes divisible by 3. Because of this, only the remainder of each stone modulo 3 matters, allowing the problem to be simplified into three groups: 0, 1, and 2.
Game theory and counting-based greedy problems similar to Stone Game IX do appear in FAANG-style interviews. Interviewers often expect candidates to recognize patterns like modulo grouping and reason about optimal play.
A simple counting array of size three is sufficient to store how many stones have remainders 0, 1, and 2. This keeps the solution efficient and avoids the need for more complex data structures.
The optimal approach counts stones by their remainder when divided by 3 and analyzes the game using these counts. Instead of simulating every move, the solution uses game theory observations about how remainders interact to determine if Alice can force a win.