Java O(n) two solutions
We are only interested in number of stones with some resildual for each modulo 3.\n\n\npublic boolean stoneGameIX(int[] stones) {\n        int a = 0, b = 0, c =
We are only interested in number of stones with some resildual for each modulo 3.\n\n```\npublic boolean stoneGameIX(int[] stones) {\n        int a = 0, b = 0, c = 0;\n        for (int stone : stones) {\n            switch (stone % 3) {\n                case 0 -> a++;\n                case 1 -> b++;\n                case 2 -> c++;\n            }\n        }\n        return solve(a, b, c);\n    }\n```\n\nWe can\'t see that after the first move, the game is already decided and moves of players doesn\'t change anything.\nThere are two possible scenarios:\n**1). 1,1,2,1,2,1,2,1,2.... until someone will run out of moves or no stone will  be left\n2). 2,2,1,2,1,2,1,2,1,... until someone will run out of moves or no stone will  be left**\n\nAlso players can take stones with values modulo 3 equal 0.\n\nSo we can simulate game for two possible first moves.\n\n```\nboolean solve(int a, int b, int c) {\n\treturn b != 0 && check(a, b - 1, c, 1) || c != 0 && check(a, b, c - 1, 2);\n}\n\nboolean check(int a, int b, int c, int sum) {\n        boolean first = true;\n        while (a != 0 || b != 0 || c != 0) {\n            if (c != 0 && sum != 1) {\n                c--;\n                first = !first;\n                sum += 2;\n                sum %= 3;\n            } else if (b != 0 && sum != 2) {\n                b--;\n                first = !first;\n                sum += 1;\n                sum %= 3;\n            } else if (a != 0) {\n                a--;\n                first = !first;\n            } else break;\n        }\n        if (a + b + c == 0) return false;\n        else return first;\n    }\n```\n\nNow we can remove simulating the game and solve it like this:\n\n```\nboolean solve(int a, int b, int c) {\n        a &= 1;\n        if (b == 0 && c == 0) return false; //first player are forced to take stone with value equals 0 modulo 3\n        if (b == 0 && c <= 2) return false; //Bob can easily grab all stones with value equals 2 modulo 3\n        if (c == 0 && b <= 2) return false; //Bob can easily grab all stone with value equals 1 modulo 3\n        if (b == 0) return a == 1; // Parity of number of stones with value 0 modulo 3 will decide who will be forced to take third stone with 2 modulo 3\n        if (c == 0) return a == 1; // Parity of number of stones with value 0 modulo 3 will decide who will be forced to take third stone with 1 modulo 3\n\n        if (a == 0 && b == 1 && c > 0) return true; // Alice takes 1. Now Bob will be forced to take 2.\n        if (a == 0 && c == 1 && b > 0) return true; //Alice takes 2. Now Bob will be forced to take 1\n        if (a == 0 && b >= 2 && c + 1 > b) return true; // Playing the first sequence Bob will be forced to take 2.\n        if (a == 0 && c >= 2 && b + 1 > c) return true; // Playing the second sequence Bob will be forced to take 1.\n\n        if (a == 1 && b >= 3 && c + 2 < b) return true; // Playing the first sequence Bob will be forced to take 1.\n        if (a == 1 && c >= 3 && b + 2 < c) return true; // Playing the second sequence Bob will be forced to take 2\n        return false; //we checked all possible ways for Alice to win a game\n    }\n```\n\n\n
[]