LeetCode 2029 - Stone Game IX

The problem describes a turn-based game between Alice and Bob with a row of stones, each having a numeric value. On each turn, a player removes any stone of their choice.

leetcodemediumarraymathgreedycountinggame-theory

LeetCode Problem 2029

Difficulty: 🟡 Medium
Topics: Array, Math, Greedy, Counting, Game Theory

Solution

Problem Understanding

The problem describes a turn-based game between Alice and Bob with a row of stones, each having a numeric value. On each turn, a player removes any stone of their choice. The game has a losing condition based on the sum of removed stones: if the cumulative sum of all removed stones becomes divisible by 3 at any point, the player who made that move loses. Additionally, if all stones are removed and the sum is not divisible by 3, Bob wins automatically.

The input stones is a list of integers representing the values of each stone. The output is a boolean indicating whether Alice, the first player, can guarantee a win if both players play optimally.

Constraints indicate that there can be up to $10^5$ stones and each stone value can be up to $10^4$. This rules out any brute-force approach that attempts to simulate every sequence of moves, because the number of sequences grows factorially with the number of stones. Edge cases include a single stone, all stones with the same modulo 3 value, or configurations where only specific sequences can lead to a win.

The key insight is that the game outcome depends not on the absolute values of the stones but on their remainders modulo 3. This transforms the problem from a complicated sequence of moves to a counting problem based on the categories of stones: those equivalent to 0, 1, or 2 modulo 3.

Approaches

The naive approach is to simulate every possible sequence of moves. On each turn, you recursively remove a stone, update the sum, and check if it is divisible by 3. This approach is correct because it exhaustively considers all possibilities. However, it has factorial time complexity $O(n!)$ and is infeasible for $n$ up to $10^5$.

The optimal approach relies on the modulo 3 classification. Stones with value divisible by 3 (mod 3 == 0) can only change whose turn it is without affecting the sum modulo 3. Stones with value 1 or 2 modulo 3 directly influence the sum. The problem reduces to a counting game: Alice can force a win if she can maintain an advantage in alternating modulo 1 and 2 stones while not being forced to take a stone that makes the sum divisible by 3. A few key observations emerge: if there are no stones of either modulo 1 or modulo 2, Alice loses if both counts are nonzero but the minimum count is 1, and if there are more than one of each modulo, Alice can generally win by careful alternation.

Approach Time Complexity Space Complexity Notes
Brute Force O(n!) O(n) Simulate every sequence of removals and check sum divisibility; correct but infeasible for large n
Optimal O(n) O(1) Count stones by modulo 3 and use game-theory insight to determine winner without simulating moves

Algorithm Walkthrough

  1. Initialize three counters: count0, count1, and count2 for stones whose values modulo 3 are 0, 1, and 2, respectively.
  2. Iterate through the stones array and increment the corresponding counter for each stone based on stone % 3.
  3. If count0 is even, the presence of stones divisible by 3 does not force the first player to lose; the game reduces to alternation between modulo 1 and 2 stones.
  4. If count0 is odd, the player forced to take the first divisible-by-3 stone will lose if no other options exist. This can shift the winning strategy.
  5. Apply the following winning conditions:
  • If either count1 == 0 or count2 == 0, Alice can only win if both are not zero and count0 is odd; otherwise she loses.
  • Otherwise, Alice can win if the difference between count1 and count2 is greater than 2.
  1. Return true if Alice can force a win under these conditions; otherwise return false.

The reasoning works because modulo 3 arithmetic captures exactly the condition that determines a loss. By counting stones by modulo, we eliminate the need to simulate all sequences while preserving the decision logic of optimal play.

Python Solution

from typing import List

class Solution:
    def stoneGameIX(self, stones: List[int]) -> bool:
        count0 = count1 = count2 = 0
        for stone in stones:
            if stone % 3 == 0:
                count0 += 1
            elif stone % 3 == 1:
                count1 += 1
            else:
                count2 += 1
        
        if count0 % 2 == 0:
            return count1 > 0 and count2 > 0
        else:
            return abs(count1 - count2) > 2

The code first counts the stones by their modulo 3 values. The even/odd status of count0 determines whether the zero-stones introduce a parity shift. The final condition checks the strategic difference between modulo 1 and 2 stones to see if Alice can maintain control and avoid being forced to lose.

Go Solution

func stoneGameIX(stones []int) bool {
    count0, count1, count2 := 0, 0, 0
    for _, stone := range stones {
        mod := stone % 3
        if mod == 0 {
            count0++
        } else if mod == 1 {
            count1++
        } else {
            count2++
        }
    }
    
    if count0%2 == 0 {
        return count1 > 0 && count2 > 0
    }
    return abs(count1 - count2) > 2
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

The Go version mirrors the Python logic. Differences include explicit modulo computation, initialization, and the use of a helper function for abs. Go handles slices and integer arithmetic without extra overhead, making the solution straightforward.

Worked Examples

Example 1: stones = [2,1]

Stone Mod 3 Counts after processing
2 2 count2 = 1
1 1 count1 = 1

count0 = 0 (even), count1 = 1, count2 = 1 → both > 0, Alice wins → returns true.

Example 2: stones = [2]

Stone Mod 3 Counts after processing
2 2 count2 = 1

count0 = 0 (even), count1 = 0, count2 = 1 → one count zero, Alice cannot force a win → returns false.

Example 3: stones = [5,1,2,4,3]

Stone Mod 3 Counts
5 2 count2 = 1
1 1 count1 = 1
2 2 count2 = 2
4 1 count1 = 2
3 0 count0 = 1

count0 = 1 (odd), abs(count1 - count2) = abs(2-2) = 0 → ≤ 2 → Alice loses → returns false.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass through the stones to count modulo categories
Space O(1) Only three counters are maintained, independent of n

The algorithm achieves optimal efficiency by avoiding simulation and using constant extra space. Counting modulo 3 captures all game-relevant information.

Test Cases

# Provided examples
assert Solution().stoneGameIX([2,1]) == True  # Alice can win
assert Solution().stoneGameIX([2]) == False  # Alice cannot win
assert Solution().stoneGameIX([5,1,2,4,3]) == False  # Alice cannot win

# Edge cases
assert Solution().stoneGameIX([3,3,3]) == False  # Only divisible by 3 stones
assert Solution().stoneGameIX([1,1,1]) == False  # Only modulo 1 stones
assert Solution().stoneGameIX([2,2,2]) == False  # Only modulo 2 stones
assert Solution().stoneGameIX([1,2,1,2,1,2]) == True  # Balanced modulo 1 and 2
assert Solution().stoneGameIX([1,2,3,3,3]) == True  # Mix with zeros even
Test Why
[2,1] Small array with two stones, Alice can force sum divisible by 3 on Bob's turn
[2] Single stone, Alice loses automatically
[5,1,2,4,3] Mix of stones, Alice loses because modulo difference ≤ 2 with odd zeros
[3,3,3] Only divisible by 3 stones, forces Alice to lose
[1,1,1] Only modulo 1 stones, Alice cannot create forced loss for Bob
[2,2,