2029. Stone Game IX

Description

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^th 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.

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.

Constraints:

1 <= stones.length <= 10⁵
1 <= stones[i] <= 10⁴

Solutions

Solution 1: Greedy + Case Discussion

Since the player's goal is to ensure the total value of the removed stones is not divisible by $3$, we only need to consider the remainder of each stone's value when divided by $3$.

We use an array $\textit{cnt}$ of length $3$ to maintain the count of the current remaining stones' values modulo $3$, where $\textit{cnt}[0]$ represents the count of stones with a remainder of $0$, and $\textit{cnt}[1]$ and $\textit{cnt}[2]$ respectively represent the counts of stones with remainders of $1$ and $2$.

In the first round, Alice cannot remove stones with a remainder of $0$, as this would make the total value of the removed stones divisible by $3$. Therefore, Alice can only remove stones with a remainder of $1$ or $2$.

First, let's consider the case where Alice removes a stone with a remainder of $1$. If Alice removes a stone with a remainder of $1$, the remainder of the total value of stones $0$ against $3$ will not change, so stones with a value remainder of $0$ can be removed in any round, which we will not consider for now. Thus, Bob can only remove stones with a remainder of $1$, followed by Alice removing stones with a remainder of $2$, and so on, in the sequence $1, 1, 2, 1, 2, \ldots$. In this scenario, if the final round is odd and there are still remaining stones, then Alice wins; otherwise, Bob wins.

For the case where Alice removes a stone with a remainder of $2$ in the first round, we can draw a similar conclusion.

The time complexity is $O(n)$, where $n$ is the length of the array $\textit{stones}$. The space complexity is $O(1)$.

Python3JavaC++GoTypeScriptJavaScript

class Solution:
    def stoneGameIX(self, stones: List[int]) -> bool:
        def check(cnt: List[int]) -> bool:
            if cnt[1] == 0:
                return False
            cnt[1] -= 1
            r = 1 + min(cnt[1], cnt[2]) * 2 + cnt[0]
            if cnt[1] > cnt[2]:
                cnt[1] -= 1
                r += 1
            return r % 2 == 1 and cnt[1] != cnt[2]

        c1 = [0] * 3
        for x in stones:
            c1[x % 3] += 1
        c2 = [c1[0], c1[2], c1[1]]
        return check(c1) or check(c2)

class Solution {
    public boolean stoneGameIX(int[] stones) {
        int[] c1 = new int[3];
        for (int x : stones) {
            c1[x % 3]++;
        }
        int[] c2 = {c1[0], c1[2], c1[1]};
        return check(c1) || check(c2);
    }

    private boolean check(int[] cnt) {
        if (--cnt[1] < 0) {
            return false;
        }
        int r = 1 + Math.min(cnt[1], cnt[2]) * 2 + cnt[0];
        if (cnt[1] > cnt[2]) {
            --cnt[1];
            ++r;
        }
        return r % 2 == 1 && cnt[1] != cnt[2];
    }
}

class Solution {
public:
    bool stoneGameIX(vector<int>& stones) {
        vector<int> c1(3);
        for (int x : stones) {
            ++c1[x % 3];
        }
        vector<int> c2 = {c1[0], c1[2], c1[1]};
        auto check = [](auto& cnt) -> bool {
            if (--cnt[1] < 0) {
                return false;
            }
            int r = 1 + min(cnt[1], cnt[2]) * 2 + cnt[0];
            if (cnt[1] > cnt[2]) {
                --cnt[1];
                ++r;
            }
            return r % 2 && cnt[1] != cnt[2];
        };
        return check(c1) || check(c2);
    }
};

func stoneGameIX(stones []int) bool {
    c1 := [3]int{}
    for _, x := range stones {
        c1[x%3]++
    }
    c2 := [3]int{c1[0], c1[2], c1[1]}
    check := func(cnt [3]int) bool {
        if cnt[1] == 0 {
            return false
        }
        cnt[1]--
        r := 1 + min(cnt[1], cnt[2])*2 + cnt[0]
        if cnt[1] > cnt[2] {
            cnt[1]--
            r++
        }
        return r%2 == 1 && cnt[1] != cnt[2]
    }
    return check(c1) || check(c2)
}

function stoneGameIX(stones: number[]): boolean {
    const c1: number[] = Array(3).fill(0);
    for (const x of stones) {
        ++c1[x % 3];
    }
    const c2: number[] = [c1[0], c1[2], c1[1]];
    const check = (cnt: number[]): boolean => {
        if (--cnt[1] < 0) {
            return false;
        }
        let r = 1 + Math.min(cnt[1], cnt[2]) * 2 + cnt[0];
        if (cnt[1] > cnt[2]) {
            --cnt[1];
            ++r;
        }
        return r % 2 === 1 && cnt[1] !== cnt[2];
    };
    return check(c1) || check(c2);
}

function stoneGameIX(stones) {
    const c1 = Array(3).fill(0);
    for (const x of stones) {
        ++c1[x % 3];
    }
    const c2 = [c1[0], c1[2], c1[1]];
    const check = cnt => {
        if (--cnt[1] < 0) {
            return false;
        }
        let r = 1 + Math.min(cnt[1], cnt[2]) * 2 + cnt[0];
        if (cnt[1] > cnt[2]) {
            --cnt[1];
            ++r;
        }
        return r % 2 === 1 && cnt[1] !== cnt[2];
    };
    return check(c1) || check(c2);
}

Solution 2: Simulation

TypeScriptJavaScript

function stoneGameIX(stones: number[]): boolean {
    if (stones.length === 1) return false;

    const cnt = Array(3).fill(0);
    for (const x of stones) cnt[x % 3]++;

    const check = (x: number, cnt: number[]): boolean => {
        let c = 1;
        if (--cnt[x] < 0) return false;

        while (cnt[1] || cnt[2]) {
            if (cnt[x]) {
                cnt[x]--;
                x = x === 1 ? 2 : 1;
            } else return (c + cnt[0]) % 2 === 1;
            c++;
        }

        return false;
    };

    return check(1, [...cnt]) || check(2, [...cnt]);
}

function stoneGameIX(stones) {
    if (stones.length === 1) return false;

    const cnt = Array(3).fill(0);
    for (const x of stones) cnt[x % 3]++;

    const check = (x, cnt) => {
        let c = 1;
        if (--cnt[x] < 0) return false;

        while (cnt[1] || cnt[2]) {
            if (cnt[x]) {
                cnt[x]--;
                x = x === 1 ? 2 : 1;
            } else return (c + cnt[0]) % 2 === 1;
            c++;
        }

        return false;
    };

    return check(1, [...cnt]) || check(2, [...cnt]);
}

2029. Stone Game IX

Description

Solutions

Solution 1: Greedy + Case Discussion

Solution 2: Simulation

Comments