#2029

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Stone Game IX

In the Stone Game IX problem, Alice and Bob take turns removing stones, and Alice wins if the sum of removed stones is divisible by 3.

array math greedy counting game theory

Problem Statement

Alice and Bob are playing a game with a row of n stones, each with an associated value. Alice starts first, and the players take turns removing stones from the row. The game ends when the sum of the removed stones is divisible by 3. If this occurs during Bob's turn, Bob loses and Alice wins the game. If Alice removes all stones without satisfying this condition, Bob wins automatically.

The task is to determine, assuming optimal play from both players, whether Alice will win the game. You are provided with an integer array stones, where stones[i] represents the value of the ith stone. Your goal is to return true if Alice wins, or false if Bob wins.

Examples

Example 1

Input: stones = [2,1]

Output: true

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

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

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 <= 105
1 <= stones[i] <= 104

Solution Approach

Track Divisibility of the Sum

The key idea is to track the sum of the stones removed by both players. Alice needs to ensure that the total sum of removed stones is divisible by 3 at the right time. By maintaining the sum modulo 3, the game can be reduced to validating whether this sum becomes divisible by 3 when Bob is forced to remove the last stone.

Greedy Choices Based on Available Stones

Given the limited number of stones left, the players should make greedy choices to either maximize or minimize the sum of removed stones to ensure they are not forced into a losing state. Understanding how each stone affects the remainder when divided by 3 is critical to avoid situations where Alice ends up losing.

Invariant Validation with Modulo 3

The optimal strategy revolves around understanding the possible remainders when the sum of removed stones is divided by 3. This insight helps in predicting the flow of the game based on the sum's modulo value at each step. By tracking the invariant that the sum of removed stones must follow, players can adjust their strategy accordingly.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time and space complexity depend on the approach used to simulate the game. A brute-force approach would involve checking all possible moves, leading to exponential time complexity. However, with an optimized greedy approach, the problem can be solved in linear time by maintaining the modulo sum, with space complexity proportional to the number of stones in the input array.

What Interviewers Usually Probe

Look for the candidate's understanding of greedy strategies and game theory principles.
Evaluate the candidate's ability to reduce the problem to manageable steps using mathematical properties like modulo.
Assess how well the candidate tracks state transitions and invariants during the game.

Common Pitfalls or Variants

Common pitfalls

Forgetting to properly track the sum modulo 3, leading to incorrect results when determining if the sum is divisible by 3.
Assuming that the game can be solved without considering the sequence of moves by both players, which might lead to overlooking certain optimal strategies.
Not recognizing that the game's outcome depends on both players making the best possible moves, requiring a deeper understanding of optimal play.

Follow-up variants

Consider a version where players can remove multiple stones per turn. This would introduce more complex strategic elements to the game.
What if the sum of the removed stones has to be divisible by 5 instead of 3? This variant would alter the modulo strategy and game flow.
Introduce a rule where the player who makes the first move after a certain number of turns must remove two stones instead of one. This change would impact the optimal strategy.

FAQ

How do I know if Alice will win in the Stone Game IX?

You can determine if Alice wins by analyzing the sum of removed stones modulo 3. If Alice can force the sum to become divisible by 3 during Bob's turn, she wins.

What is the main challenge in solving Stone Game IX?

The main challenge is tracking the sum of removed stones and ensuring that the players make moves that align with the divisibility condition, avoiding losing states.

How does the modulo operation help in this problem?

The modulo operation helps in tracking the remainder of the sum of removed stones. By focusing on the modulo 3 value, you can predict the outcome of the game efficiently.

What happens if there are no stones left to remove?

If there are no stones left, Bob wins automatically, regardless of the state of the game.

Can you simplify the game strategy for Stone Game IX?

The strategy revolves around tracking the sum of removed stones modulo 3, and making moves that ensure Alice can control the sum to force a win.

terminal

Solution

Solution 1: Greedy + Case Discussion

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

class Solution:
    def stoneGameIX(self, stones: List[int]) -> bool:
        def check(cnt: List[int]) -> bool:
            if cnt[1] == 0:
                return False
            cnt[1] -= 1
            r = 1 + min(cnt[1], cnt[2]) * 2 + cnt[0]
            if cnt[1] > cnt[2]:
                cnt[1] -= 1
                r += 1
            return r % 2 == 1 and cnt[1] != cnt[2]

        c1 = [0] * 3
        for x in stones:
            c1[x % 3] += 1
        c2 = [c1[0], c1[2], c1[1]]
        return check(c1) or check(c2)

Solution 2: Simulation

#### TypeScript

class Solution:
    def stoneGameIX(self, stones: List[int]) -> bool:
        def check(cnt: List[int]) -> bool:
            if cnt[1] == 0:
                return False
            cnt[1] -= 1
            r = 1 + min(cnt[1], cnt[2]) * 2 + cnt[0]
            if cnt[1] > cnt[2]:
                cnt[1] -= 1
                r += 1
            return r % 2 == 1 and cnt[1] != cnt[2]

        c1 = [0] * 3
        for x in stones:
            c1[x % 3] += 1
        c2 = [c1[0], c1[2], c1[1]]
        return check(c1) or check(c2)

Continue Practicing

#1686 stone game vi #1561 maximum number of coins you can get #2038 remove colored pieces if both neighbors are the same color