[C++] O(n). Short & Clean. Explained.
This involved some massive case-work! However, the final code is clean. Here\'s some key observations that can help :\n\n- Reduce all numbers to remainders of 3
This involved some massive case-work! However, the final code is clean. Here\'s some key observations that can help :\n\n- Reduce all numbers to remainders of 3. (4 + 1) % 3 has the same effect as ((4 % 3) + (1 % 3)) % 3. This makes comparison much easier as it boils down to counts of 0\'s, 1\'s and 2\'s.\n- Realize that a multiple of 3 (i.e. mod value of 0) does not change the net sum. HOWEVER, it can be used to flip the winner - but only if it\'s an odd number of times. This is because, if it\'s an even number of times, each player can play it equally and it won\'t make any difference to the outcome. However, with an odd number of occurances, it can flip the winner.\n- If there are no 1\'s (i.e. no 1, 4, 7, etc.) then all you have are 2\'s\n\t- If there\'s less than three 2\'s, Bob always wins (since they both play one or two 2\'s and eventually the game runs out while never meeting a multiple of 3). \n\t- If there are three or more 2\'s, then Bob wins as well, UNLESS there\'s a flip available.\n- Same as above if there are no 2\'s.\n- Next, if the gap between 1\'s and 2\'s exceeds 2, then Alice always wins. This is because Alice plays the minority number first. Then Bob is forced to play the same minority number, then Alice plays the majority number, until that number is exhausted (on Bob\'s turn). If there is a flip available, then Alice plays the majority number first, leading to the same outcome.\n- Finally, if none of the above work, Alice will be the default winner, unless there is a flip involved.\n- Phew. I think the code\'s a lot shorter than this explanation.\n\n```\n#define ALICE true\n#define BOB false\n\nclass Solution {\npublic:\n    bool stoneGameIX(vector<int>& stones) {\n        vector<int> a(3, 0);\n        for (auto &x : stones)\n            a[x % 3]++;\n        bool flip = (a[0] % 2 > 0);\n        if (!a[1])\n            return (a[2] < 3 ? BOB : flip);\n        if (!a[2])\n            return (a[1] < 3 ? BOB : flip);\n        if (abs(a[1] - a[2]) > 2)\n            return ALICE;\n        return !flip;\n    }\n};\n```
[]