O(n) Rust solution with explanation using state machine
The state of the game is tied to the sum of the removed stones modulo 3. The stones\' values can also be converted to modulo 3. \n\nThus there are three possibl
The state of the game is tied to the sum of the removed stones modulo 3. The stones\' values can also be converted to modulo 3. \n\nThus there are three possible states for the game to be in: 0, 1, and 2 and three possible stone types: 0, 1, 2. We can represent the game as a DFA with starting state 0 (initially the sum is 0) and with transitions between states representing what would happen if a player removed such a stone from the remaining stones. The final state is state 0 again as the game ends as soon as the first person reaches a sum divisible by 3. \n\n![image](https://assets.leetcode.com/users/images/40a02a94-6574-4430-b9e8-fa5da3ab161e_1651300896.212427.png)\n\n\nWe also add two special edges from node-1 and node-2 that uses a special stone `$` that transitions to the final state 0. We implicitly enforce the rule that this symbol appears after all the existing stones have been used up. Moving through any of the other edges also toggles the parity of the players but this special edge sets the player to Alice. The player that ends up in the final state 0 loses. \n\nNow, for a non-trivial game to begin there must be at least one stone 1 or one stone 2. These are used to oscillate between these states 1 and 2 and to formally end the game from these states. 0 stones are useful for skipping turns and hence they can toggle the parity of the players. Let `n0`, `n1` and `n2` represent the counts of stones 0, 1 and 2 respectively. \n\nLet us take `nx` and `nn` to be the respective maximum and minimum of `n1` and `n2`. WLOG (only because this is a ring modulo 3) let us use state/stone `x` to represent that state/stone which corresponds to `nx` stones and state/stone `n` to represent that state/stone which corresponds to `nn`. Stone `x` takes us from state `x` to state `n` and vice versa. Stone `n` in state `x` is "poisonous" as it can be used to formally end the game, and vice versa. \n\nAs the modulus operation forms a ring that is closed under addition, we can consider stone-0 parity switching operation separately from the oscillating operation between nodes `x` and `n`. Since both players are playing optimally, neither of them would want to prematurely terminate the game with a "poisonous" stone in the middle and they will try to battle it out till there is no option left but for one of the players to take the poision stone and lose the game or Alice loses the game when all the stones run out. \n\nSay we first start off the game with stone `x`. Now we are left with `nx-1` stones of type `x` and we are also in state `x`.\n\nFor oscillating between `x` and `n` we have three cases when it comes to where we finally land and what the player\'s parity might be:\n\n**Case-1:** `nx-1 < nn`\nThis case is possible only when `nx == nn`. So `nx-1 = nn-1`. \n\nIn this case we will end up getting stuck at state `x` back again with player Bob to make the next move, as we will eventually run out of `x` stones to go back to state `n`. And we will have one extra stone of type `n` for the final player to lose the game. Till that time we toggle the parity of the players until we run out of stone-0. \n\n**Case-2:** `nx-1 == nn`\nIn this case we will run out of stones as we vacillate and land at state x again with Bob to make the next move, and after toggling the parity of the players with stone 0s, there won\'t be a final "poison pill" for the unlucky player to formally end the game with. This means that Alice will lose the game according to the rules. \n\n**Case-3:** `nx-1 > nn`\nIn this case there is a subtle edge case where we need to enforce `nx - nn > 2` for us to finally land in state `n` with Alice to make the next move, and with at least one "poison" stone `x` using which one of the players can formally enter state 0 after toggling their parities with stone 0. Otherwise if `nx == nn + 2` we will end up in state `n` without the poison stone `x` to end the game. This way Alice will end up losing the game inevitably after all the 0 stones are used up.\n\nWhenever we have a poison option the parity of the player (Alice = 0; Bob = 1) who is to make the next move must *not* match the parity of `n0` in order for them to win. This means that in case-1 and case-2 we want `n0%2 == 0` and in case-3 we want `n0%2 == 1`. \n\nSo putting all this together we see that if we pick `x` stone first to start off the game, we win only if `(nx > nn + 2 && n0%2 == 1) || (nx == nn && nn > 0 && n0%2 == 0)`. Note that the condition for entry that `nx > 0` is satisfied in both of these because `nn > 0`. \n\nIf we start off with stone `n` after entry into state `n` we will have `nn-1` stones of type `n`. Now we only have the one case for oscillation: `nn-1 < nx`, which will always be true. So similar to case-1 we will end up in state `n` back again with player Bob to make the next move and with at least one poison stone of type `x` to formally end the game. \n\nSo we have `(nn > 0 && n0%2 == 0)` for Alice to win. Note that the case where `nx-1 == nn` where Alice would have definitely lost had she picked stone `x` first turns into a possible win for Alice if she just picks stone `n` first. And of course, when `nx == nn` it does not matter which stone we pick. \n\nCombining the two together we get this simplified condition:\n\n`(nx > nn + 2 && n0%2 == 1) || (nn > 0 && n0%2 == 0)`\n\nThe following is the Rust code implementing this logic\n```rust\nuse std::cmp::{min, max};\n\nimpl Solution {\n    pub fn stone_game_ix(stones: Vec<i32>) -> bool {\n        let (n0, n1, n2) = stones.into_iter()\n                            .map(|stone| ((stone%3 == 0), (stone%3 == 1), (stone%3 == 2))) // tuple of bool\n                            .map(|(n0, n1, n2)| (n0 as usize, n1 as usize, n2 as usize)) // tuple of 1s for true and 0s for false\n                            .fold((0, 0, 0), |(nacc0, nacc1, nacc2), (n0, n1, n2)| (nacc0+n0, nacc1+n1, nacc2+n2));\n        \n        let nx = max(n1, n2);\n        let nn = min(n1, n2);\n        \n        (nn != 0 && n0%2 == 0) || (nx > nn + 2 && n0%2 == 1)\n    }\n}\n```
['Rust']