# 2029. Stone Game IX

Question link is here.

# Question

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

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 andfalse if Bob wins.

Example 1:

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:

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:

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.

# Solution

The trick here is that both alice and bob plays optimally in the game. So now let analysis this game.

The values can be divied into three groups:

• Group1: Mod = 0
• Group2: Mod = 1
• Group3: Mod = 2

Alice is always the one starts the game, so she only has two choices: choose from group 1 or group 2. And after alice choose, the safest way for bob is choose from group 1. And alice still choose from group 1 until there is no stone left in group 1.

And now, there would be two possible case1:

• Case 1: If group 1 has even number of stones, bob will make the next move.
• Case 2: Otherwise, alice will make the next move.

# Case 1:

As long as group2 != 0 and group1 != 0, Alice can always win, because she can choose whether to start with 1 or 2. Say that there are 5 stones from group2, and 6 stones at group3. So the sequence would be 1 -> 1 -> 2 -> 1 -> 2 -> 1 -> 2 -> 1 -> 2 -> 2. So bob lose the game. Otherwise, no matter how alice chooses, she loses.

# Case 2:

As long as the diff of group2 and group 3 > 2, Alice can always win because alice can always start from the group with more stones. Say that there are 2 stones from group2, and 5 stones at group3.

Alice -> Alice -> Bob -> Alice -> Bob -> Alice -> Bob

2 -> 2 -> 1 -> 2 -> 1 -> 2 -> 2

However, it there are only 4 stones at group3, Alice would lose at the last two step because all stones are used.

# Code

class Solution {
    public boolean stoneGameIX(int[] stones) {
        if(stones.length == 1)
            return false;
        int diff = 0;
        int[] arr = new int[]{0,0,0};
        for(int i = 0; i < stones.length; i++) {
            arr[stones[i] % 3] += 1;
        }
        if(arr[1] == 0 && arr[2] == 0 && arr[0] != 0)
            return false;
        if(arr[0] % 2 == 0){
            if(arr[1] != 0 && arr[2] != 0)
                return true;
            else
                return false;
        } else {
            diff = Math.abs(arr[1] - arr[2]);
            if(diff > 2)
                return true;
            else
                return false;
        }
    }
}

Time Complexity: $O(n)$.