2029. Stone Game IX

Problem Overview

The game only cares about stone values mod 3.

Intuition

The game only cares about stone values mod 3. Playing a stone adds its residue to a running total that must stay non-zero mod 3 after each move. Type 0 never changes the residue; types 1 and 2 alternate. Counting the three residues is enough to decide whether Alice has a winning strategy.

Algorithm

1count[r] = number of stones with stone % 3 == r.
2If count[0] is even: Alice wins iff both count[1] and count[2] are at least 1.
3If count[0] is odd: Alice wins iff |count[1] - count[2]| > 2.
4Otherwise Bob wins (return false).

Example Walkthrough

Input: stones = [2, 1]

1.Residues: 2 and 1 -> counts [0, 1, 1].
2.count[0] is even and both type 1 and type 2 exist, so Alice wins.
3.Alice plays one residue; Bob is forced to play the other and the sum becomes 0 mod 3.

Output: true

Common Pitfalls

•Do not simulate every move order - n can be 1e5; the closed counting rule is enough.
•stone % 3 == 0 acts like a pass on the residue but still consumes a turn.
•If either type 1 or type 2 is missing while count[0] is even, Alice cannot force a win.
•Bob wins automatically if stones run out without a losing move.

2029.cs

// Approach: Only stone % 3 matters. Type 0 does not change the running XOR-sum
// mod 3; types 1 and 2 flip between residues. With optimal play, Alice wins
// iff (even count of 0s and both 1 and 2 exist) or (odd count of 0s and
// |count[1] - count[2]| > 2).
// Complexity: O(n) time and O(1) space.
public class Solution
{
    public bool StoneGameIX(int[] stones)
    {
        int[] count = new int[3];

        foreach (var stone in stones)
            ++count[stone % 3];

        if (count[0] % 2 == 0)
            return Math.Min(count[1], count[2]) > 0;
        return Math.Abs(count[1] - count[2]) > 2;
    }
}

Was this solution helpful?