Problem Description

Alice and Bob are playing a stone game. There are n stones in a row, each with an associated value given in the array stones, where stones[i] represents the value of the i-th stone.

The game proceeds as follows:

• Alice and Bob take turns removing stones, with Alice going first
• On each turn, a player can remove any one stone from the remaining stones
• A player loses if after their move, the sum of all removed stones becomes divisible by 3
• If all stones are removed and no one has lost yet, Bob wins automatically (even if it's Alice's turn)

Both players play optimally, meaning they always make the best possible move to try to win.

Return true if Alice wins the game, and false if Bob wins.

The key insight is that since we only care about divisibility by 3, we only need to track the remainder when each stone's value is divided by 3. The game becomes a strategic battle where players must carefully choose which stones to remove to avoid making the total sum divisible by 3.

For example, if the running sum of removed stones is currently 2 (mod 3), removing a stone with value 1 (mod 3) would make the total 0 (mod 3), causing that player to lose. The solution involves counting stones by their remainders (0, 1, or 2) and simulating the optimal play patterns to determine the winner.

Intuition

Since we only care about whether the sum is divisible by 3, we can simplify the problem by only considering each stone's value modulo 3. This means every stone falls into one of three categories: remainder 0, 1, or 2.

The crucial observation is that stones with remainder 0 don't affect whether the sum is divisible by 3 - they can be freely removed without changing the game state modulo 3. So these stones essentially just add extra turns to the game.

Now let's think about Alice's first move. She cannot pick a stone with remainder 0, as that would immediately make the sum divisible by 3 (starting from 0), causing her to lose. So Alice must start with either a stone of remainder 1 or remainder 2.

If Alice picks a stone with remainder 1, the running sum becomes 1 (mod 3). Now Bob needs to avoid making it 0 (mod 3), so:

• Bob cannot pick remainder 2 (as 1 + 2 = 0 mod 3)
• Bob can only pick remainder 1, making the sum 2 (mod 3)
• Then Alice must pick remainder 2 (to avoid 2 + 1 = 0 mod 3), returning to sum 1 (mod 3)
• This creates a pattern: 1, 1, 2, 1, 2, 1, 2...

Similarly, if Alice starts with remainder 2, the pattern becomes: 2, 2, 1, 2, 1, 2, 1...

The key insight is that after the initial moves, the game follows a predictable pattern where players alternate between picking stones of remainder 1 and 2. The winner depends on:

1. Whether there are enough stones to sustain the required pattern
2. Whether the total number of moves (including remainder 0 stones) is odd or even

Since both players play optimally, Alice will choose the starting move (remainder 1 or 2) that gives her the best chance to win. The solution checks both possibilities and returns true if either leads to Alice's victory.

Learn more about Greedy and Math patterns.

Solution Approach

The solution implements the game simulation by counting stones based on their remainder when divided by 3, then checking both possible starting moves for Alice.

First, we count the stones by their remainders:

• cnt[0] = count of stones with value % 3 == 0
• cnt[1] = count of stones with value % 3 == 1
• cnt[2] = count of stones with value % 3 == 2

The check function simulates the game when Alice starts by picking a stone with remainder 1:

1. Initial Check: If cnt[1] == 0, Alice cannot start with remainder 1, so return False.

2. Alice's First Move: Remove one stone with remainder 1 (cnt[1] -= 1), starting the game sequence.

3. Calculate Total Moves:

   • Start with 1 move (Alice's first move)
   • Add min(cnt[1], cnt[2]) * 2 moves for the alternating pattern where players pick 1, 2, 1, 2...
   • Add cnt[0] moves (stones with remainder 0 can be picked at any time)
   • This gives us r = 1 + min(cnt[1], cnt[2]) * 2 + cnt[0]

4. Handle Extra Stones: If cnt[1] > cnt[2], there's one extra stone with remainder 1 that can be picked:

   • Decrement cnt[1] and increment r by 1

5. Determine Winner: Alice wins if:

   • The total number of moves r is odd (Alice makes the last valid move)
   • AND cnt[1] != cnt[2] (ensuring the game doesn't end with all stones removed, which would make Bob win)

The main function creates two scenarios:

• c1 = [cnt[0], cnt[1], cnt[2]]: Check if Alice can win by starting with remainder 1
• c2 = [cnt[0], cnt[2], cnt[1]]: Check if Alice can win by starting with remainder 2 (by swapping cnt[1] and cnt[2])

Alice wins if either starting strategy leads to victory: return check(c1) or check(c2)

The key insight is that after the initial moves establish the pattern, the game becomes deterministic. By counting moves and checking parity, we can determine the winner without actually simulating every possible game state.

Example Walkthrough

Let's walk through an example with stones = [5, 1, 2, 4, 3].

Step 1: Convert to remainders modulo 3

• 5 % 3 = 2
• 1 % 3 = 1
• 2 % 3 = 2
• 4 % 3 = 1
• 3 % 3 = 0

Step 2: Count stones by remainder

• cnt[0] = 1 (one stone with remainder 0)
• cnt[1] = 2 (two stones with remainder 1)
• cnt[2] = 2 (two stones with remainder 2)

Step 3: Try Strategy 1 - Alice starts with remainder 1

Check with c1 = [1, 2, 2]:

1. Alice picks remainder 1: cnt[1] = 1, running sum = 1 (mod 3)
2. Calculate moves: r = 1 + min(1, 2) * 2 + 1 = 1 + 2 + 1 = 4
   • 1 for Alice's first move
   • min(1, 2) * 2 = 2 for the alternating pattern (Bob picks 1, Alice picks 2)
   • 1 for the remainder 0 stone
3. Since cnt[1] = 1 < cnt[2] = 2, there's an extra remainder 2 stone
   • But we can't pick it (would make sum 0 mod 3)
4. Total moves r = 4 (even), and cnt[1] ≠ cnt[2]
   • Alice doesn't win with this strategy

Step 4: Try Strategy 2 - Alice starts with remainder 2

Check with c2 = [1, 2, 2] (swapping cnt[1] and cnt[2] for the check):

1. Alice picks remainder 2: cnt[2] = 1, running sum = 2 (mod 3)
2. Calculate moves: r = 1 + min(2, 1) * 2 + 1 = 1 + 2 + 1 = 4
   • Following same logic as above
3. Since cnt[1] = 2 > cnt[2] = 1, there's an extra remainder 1 stone
   • Increment r to 5 and decrement cnt[1] to 1
4. Total moves r = 5 (odd), and cnt[1] = cnt[2] = 1
   • Since they're equal, Alice doesn't win

Result: Neither strategy works, so Bob wins (return false).

The game would play out: Alice must start with either remainder 1 or 2. After the initial moves, players alternate picking stones to avoid making the sum divisible by 3. The remainder 0 stone can be picked safely at any point. With 5 total stones and the constraint patterns, Bob makes the final safe move, forcing Alice into a losing position.

Solution Implementation

Time and Space Complexity

The time complexity of this solution is O(n), where n is the length of the array stones. This is because the algorithm iterates through the entire stones array once to count the frequency of remainders when divided by 3. The loop for x in stones: c1[x % 3] += 1 processes each element exactly once, performing a constant-time modulo operation and increment for each stone.

The space complexity is O(1). The algorithm uses two fixed-size arrays c1 and c2, each containing exactly 3 elements to store the count of stones with remainders 0, 1, and 2 when divided by 3. Since the size of these arrays is constant and independent of the input size n, the space complexity remains constant. The check function also only uses a constant amount of additional space for its local variables (r and modifications to the cnt array passed by reference).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Losing Condition

A critical pitfall is misinterpreting when a player loses. Players lose when after their move the sum becomes divisible by 3, not before. This means if the current sum modulo 3 is 2, and you pick a stone with value 1 (mod 3), you lose immediately because the new sum is 0 (mod 3).

Wrong approach:

# Incorrectly checking if current sum is divisible by 3
if current_sum % 3 == 0:
    current_player_loses = True

Correct approach:

# Check if the move would make the sum divisible by 3
if (current_sum + stone_value) % 3 == 0:
    # This move would cause the player to lose

2. Incorrectly Handling the End Game Condition

Many solutions forget that if all stones are removed without anyone losing, Bob wins automatically. This is why the condition count[1] != count[2] is crucial in the check function.

Wrong approach:

def can_alice_win(count):
    # ... calculate total_moves ...
    return total_moves % 2 == 1  # Missing the end game check

Correct approach:

def can_alice_win(count):
    # ... calculate total_moves ...
    # Must check both parity AND that stones don't run out evenly
    return total_moves % 2 == 1 and count[1] != count[2]

3. Not Considering Both Starting Strategies

Alice has two viable starting strategies (picking remainder 1 or remainder 2), and the solution must check both. A common mistake is only checking one strategy.

Wrong approach:

# Only checking if Alice starts with remainder 1
return can_alice_win([cnt[0], cnt[1], cnt[2]])

Correct approach:

# Check both starting strategies
strategy_one = [cnt[0], cnt[1], cnt[2]]  # Start with remainder 1
strategy_two = [cnt[0], cnt[2], cnt[1]]  # Start with remainder 2
return can_alice_win(strategy_one) or can_alice_win(strategy_two)

4. Modifying the Original Count Array

The check function modifies the count array in place. If you pass the same array to multiple checks without copying, you'll get incorrect results.

Wrong approach:

remainder_count = [0] * 3
for stone in stones:
    remainder_count[stone % 3] += 1

# This modifies remainder_count!
result1 = can_alice_win(remainder_count)
# remainder_count is now corrupted for the second check
result2 = can_alice_win([remainder_count[0], remainder_count[2], remainder_count[1]])

Correct approach:

# Create separate copies for each strategy check
strategy_one = [remainder_count[0], remainder_count[1], remainder_count[2]]
strategy_two = [remainder_count[0], remainder_count[2], remainder_count[1]]

5. Edge Case: All Stones Have Same Remainder

When all stones have the same remainder modulo 3, special care is needed:

• If all stones have remainder 0: First player always loses
• If all stones have remainder 1 or 2: The game follows a specific pattern

Solution: The current implementation handles this correctly through the initial check if count[1] == 0: return False and the symmetric logic for strategy_two.