[C++] O(N) without simulation, explained
\nclass Solution {\npublic:\n    bool stoneGameIX(vector<int>& stones) {\n        // Alice will take the only stone. Bob wins. \n        if (stones.size() == 1)
```\nclass Solution {\npublic:\n    bool stoneGameIX(vector<int>& stones) {\n        // Alice will take the only stone. Bob wins. \n        if (stones.size() == 1) {\n            return false;\n        }\n        \n        // Collect a histogram of stone values modulo 3.\n        std::array<int, 3> histo;\n        histo.fill(0);\n        for (int val : stones) {\n            ++histo[val % 3];\n        }\n        \n        // Anything Alice picks is divisible by 3. Bob wins.\n        if ((histo[1] == 0) && (histo[2] == 0)) {\n            return false;\n        }\n        \n        // Picking a value divisible by 3 will shift the state \n        // (i.e. current remainder) to the opponent. As a result,\n        // an even number of those would not have any effect. \n        if (histo[0] % 2 == 0) {\n            // Alice will pick a value with a smaller number of occurrences. \n            // Without loss of generality, assume it is 2. \n            // Eventually the players will move the game into a state where\n            // there are one or more of 1s and the state is 2, with Bob playing next move.\n            // In this case, he would have to choose 1 and lose the game. \n            return (histo[1] > 0) && (histo[2] > 0);\n            \n            // Notice that the situation above only works when we have stones with both values.\n            // Otherwise, the game will end up in the situation where \n            // the current state is 2 and there are one or more 2s, with Bob playing next move.\n            // If there is only one stone left, Bob wins by removing it.\n            // If there are more stones, Bob removes the 2 and the game state becomes 1.\n            // Alice loses by removing the next stone. \n        }\n        \n        // When the number of stones with value divisible by 3 is odd, \n        // the game state will shift back to Alice. \n        // Assume one kind of stone has more than two counts than the other, \n        // without loss of generality, say it is 1. The game will eventually \n        // be in a state of 1 and there are at least two stones left with \n        // the same modulo 3 value (i.e. 1), with Alice playing next. \n        // Alice removes 1, transitioning the state into 2, and hand it over to Bob.\n        // There are still at least one stone with value 1, and Bob loses by removing it. \n        return std::abs(histo[1] - histo[2]) > 2;\n    }\n};\n```
[]