Problem

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.

Examples

Example 1

1
2
3
4
5
6

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

1
2
3
4

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

1
2
3
4
5
6
7
8
9

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 <= 10^5
  • 1 <= stones[i] <= 10^4

Solution

Method 1 - Count Remainders and Game Theory

Intuition

The only thing that matters is the count of stones with values mod 3 == 0, 1, or 2. Alice loses if she is forced to take the last stone or if the sum is divisible by 3 on her turn. The game can be reduced to a state machine based on the parity of the counts of stones with remainder 1 and 2.

Approach

  • Count the number of stones with value % 3 == 0, 1, and 2.
  • If either count1 == 0 or count2 == 0, Alice can only win if min(count1, count2) > 2 and max(count1, count2) > 0 and (max(count1, count2) - min(count1, count2)) > 2.
  • Otherwise, Alice wins if both count1 and count2 are at least 1 and (abs(count1 - count2) > 2 or min(count1, count2) % 2 == 1).
  • The actual winning condition is: Alice wins if count1 >= 1 and count2 >= 1 and (abs(count1 - count2) > 2 or min(count1, count2) % 2 == 1).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

#include <vector>
using namespace std;
class Solution {
public:
    bool stoneGameIX(vector<int>& stones) {
        int cnt[3] = {};
        for (int x : stones) cnt[x % 3]++;
        if (cnt[1] == 0 || cnt[2] == 0) return false;
        return abs(cnt[1] - cnt[2]) > 2 || min(cnt[1], cnt[2]) % 2 == 1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func stoneGameIX(stones []int) bool {
    cnt := [3]int{}
    for _, x := range stones {
        cnt[x%3]++
    }
    if cnt[1] == 0 || cnt[2] == 0 {
        return false
    }
    return abs(cnt[1]-cnt[2]) > 2 || min(cnt[1], cnt[2])%2 == 1
}
func abs(x int) int { if x < 0 { return -x } else { return x } }
func min(a, b int) int { if a < b { return a } else { return b } }
1
2
3
4
5
6
7
8

class Solution {
    public boolean stoneGameIX(int[] stones) {
        int[] cnt = new int[3];
        for (int x : stones) cnt[x % 3]++;
        if (cnt[1] == 0 || cnt[2] == 0) return false;
        return Math.abs(cnt[1] - cnt[2]) > 2 || Math.min(cnt[1], cnt[2]) % 2 == 1;
    }
}
1
2
3
4
5
6

fun stoneGameIX(stones: IntArray): Boolean {
    val cnt = IntArray(3)
    for (x in stones) cnt[x % 3]++
    if (cnt[1] == 0 || cnt[2] == 0) return false
    return kotlin.math.abs(cnt[1] - cnt[2]) > 2 || minOf(cnt[1], cnt[2]) % 2 == 1
}
1
2
3
4
5
6
7

def stoneGameIX(stones: list[int]) -> bool:
    cnt = [0, 0, 0]
    for x in stones:
        cnt[x % 3] += 1
    if cnt[1] == 0 or cnt[2] == 0:
        return False
    return abs(cnt[1] - cnt[2]) > 2 or min(cnt[1], cnt[2]) % 2 == 1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

pub fn stone_game_ix(stones: Vec<i32>) -> bool {
    let mut cnt = [0; 3];
    for x in stones {
        cnt[(x % 3) as usize] += 1;
    }
    if cnt[1] == 0 || cnt[2] == 0 {
        return false;
    }
    (cnt[1] - cnt[2]).abs() > 2 || cnt[1].min(cnt[2]) % 2 == 1
}
1
2
3
4
5
6

function stoneGameIX(stones: number[]): boolean {
    const cnt = [0, 0, 0];
    for (const x of stones) cnt[x % 3]++;
    if (cnt[1] === 0 || cnt[2] === 0) return false;
    return Math.abs(cnt[1] - cnt[2]) > 2 || Math.min(cnt[1], cnt[2]) % 2 === 1;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)