Formatted question description: https://leetcode.ca/all/2029.html

# 2029. Stone Game IX (Medium)

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 `i`

stone.^{th}

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

**Example 1:**

Input:stones = [2,1]Output:trueExplanation: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:falseExplanation: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:falseExplanation: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}

**Similar Questions**:

- Stone Game (Medium)
- Stone Game II (Medium)
- Stone Game III (Hard)
- Stone Game IV (Hard)
- Stone Game V (Hard)
- Stone Game VI (Medium)
- Stone Game VII (Medium)
- Stone Game VIII (Hard)
- Stone Game IX (Medium)

## Solution 1. Brain Teaser

Since we only care if the sum is divisible by `3`

, we can convert each `A[i]`

to `A[i] % 3`

, and count the frequency of `0, 1, 2`

.

Firstly, let’s ignore `0`

for now.

- If Alice starts with
`1`

, Alice and Bob have to pick`11212...`

in order. - If Alice starts with
`2`

, Alice and Bob have to pick`22121...`

in order.

For the case where Alice starts with `1`

, after matching the `11212...`

pattern, if there are still `1`

s left, Alice wins; otherwise, Bob wins.

Now, consider the `0`

s.

- If
`cnt[0]`

is even, Bob picks a`3`

, Alice can always pick another`0`

. The result won’t be changed. - If
`cnt[0]`

is odd, the final result will be reversed, expect the cases where Bob wins because all numbers are consumed.

Our goal is to get the length of the longest `112121...`

sequence plus the number of `0`

s.

If the length is odd, and there are remaining stones, then Bob has to remove a stone causing the sum to be divisible by `3`

, i.e. Alice wins; otherwise, Bob wins.

```
// OJ: https://leetcode.com/problems/stone-game-ix/
// Time: O(N)
// Space: O(1)
// Ref: https://leetcode-cn.com/problems/stone-game-ix/solution/guan-jian-zai-yu-qiu-chu-hui-he-shu-by-e-mcgv/
class Solution {
bool check(int zero, int one, int two) {
if (one == 0) return false; // Can't remove the leading one, must lose
one--;
int mn = min(one, two), len = 1 + mn * 2 + zero;
one -= mn, two -= mn;
if (one) {
++len;
--one;
}
return len % 2 && one + two;
}
public:
bool stoneGameIX(vector<int>& A) {
int c[3] = {};
for (int n : A) c[n % 3]++;
return check(c[0], c[1], c[2]) // Alice removes `1` first
|| check(c[0], c[2], c[1]); // Alice removes `2` first
}
};
```

## Solution 2.

```
// OJ: https://leetcode.com/problems/stone-game-ix/
// Time: O(N)
// Space: O(N)
// Ref: https://youtu.be/8MTch2zTOoY
class Solution {
bool win(array<int, 3> &cnt, int sum, int turn) { // turn: 0 - Alice, 1 - Bob
if (cnt[0] + cnt[1] + cnt[2] == 0) return turn == 1;
if (cnt[0]) {
cnt[0]--; // If there is `0` left, use it first (because `0` will shift the "bomb" to the other player; the players must use the `0`s anyway)
return !win(cnt, sum, 1 - turn);
} else if (sum % 3 == 1) { // If the remainder is 1, the player must pick 1
if (cnt[1]) {
cnt[1]--;
return !win(cnt, sum + 1, 1 - turn);
} return false;
} else if (cnt[2]) { // If the remainder is 2, the player must pick 2.
cnt[2]--;
return !win(cnt, sum + 2, 1 - turn);
}
return false;
}
public:
bool stoneGameIX(vector<int>& A) {
array<int, 3> cnt = {};
for (int n : A) cnt[n % 3]++;
auto tmp = cnt;
if (tmp[1]) { // If there is `1` available, Alice can try picking 1.
tmp[1]--;
if (!win(tmp, 1, 1)) return true;
}
tmp = cnt;
if (tmp[2]) { // If there is `2` available, Alice can try picking 2.
tmp[2]--;
if (!win(tmp, 2, 1)) return true;
}
return false;
}
};
```

## Solution 3.

Count the frequency of mod3 = 0, 1, 2.

Firstly, don’t consider `0`

.

- If Alice starts with
`1`

, Alice and Bob have to pick`1,1,2,1,2,...`

in order. - If Alice starts with
`2`

, Alice and Bob have to pick`2,1,2,1,2,...`

in order.

If Alice starts with `1`

, then Alice needs `1`

and Bob needs `2`

. If `1`

is much more than `2`

, then Bob is going to lose.

So, if `cnt[0] == 0`

, the result can be determined by Alice.

Now, consider the `0`

s.

- If
`cnt[0]`

is even, Bob picks a`3`

, Alice can always one another`0`

. The result won’t be changed. - If
`cnt[0]`

is odd, the final result will be reversed, expect the case where Bob wins because all numbers are consumed.

**Algorithm**:

If `cnt[1] == 0`

, Alice needs to start with `2`

.

If `cnt[2] == 0`

, Alice needs to start with `1`

.

Alice can win if `max(cnt[1], cnt[2]) > 2 && cnt[0] % 2 > 0`

. Example: `[1,1,1,3]`

.

If `cnt[0] % 2 == 0`

, Alice can win in at least one of the two options, picking the less one.

If `cnt[0] % 2 == 1`

, the result is reversed.

If `abs(cnt[1] - cnt[2]) > 2`

:

- Alice will pick
`2`

if`2`

is more - Alice will pick
`1`

if`1`

is more

If `abs(cnt[1] - cnt[2]) <= 2`

, Alice will lose for no number remaining.

```
// OJ: https://leetcode.com/problems/stone-game-ix/
// Time: O(N)
// Space: O(1)
// Ref: https://leetcode.com/problems/stone-game-ix/discuss/1500245/JavaC%2B%2BPython-Easy-and-Concise-6-lines-O(n)
class Solution {
public:
bool stoneGameIX(vector<int>& A) {
int cnt[3] = {};
for (int n : A) cnt[n % 3]++;
if (min(cnt[1], cnt[2]) == 0) return max(cnt[1], cnt[2]) > 2 && cnt[0] % 2; // If either one is `0`, Alice has to choose the non-zero one.
return abs(cnt[1] - cnt[2]) > 2 || cnt[0] % 2 == 0;
}
};
```