Observation based solution , c++ , O(N)
The important thing to observe is how can a player play optimally.\nlet\'s take the count of stones with remainder(when divided by 3) 0 , 1 & 2 .\n\ni) first pl
The important thing to observe is how can a player play optimally.\nlet\'s take the count of stones with remainder(when divided by 3) 0 , 1 & 2 .\n\ni) first player can never take a stone whose remainder is 0\nii) so to start the game Alice can take either 1 remainder stone or 2 remainder stone and that\'s the only thing that Alice has control over or is needed to find our answer\niii) after first stone with non 0 remainder is taken any 0 remainder stone can be taken that will be optimal.\n\nNow , the question is how to takes non zero remainder stones optimally ?\nThere is only 1 way of doing it. \nFirst take any two same non zero remainder stones then after it take 0 remainder and 1 remainder stones alternatively\n\nSo, we just have to observe that if starting with either of 1 remainder stone or 2 remainder stone is it possible for Alice to win and if yes return true otherwise return false;\n\n```\nclass Solution {\npublic:\n    bool stoneGameIX(vector<int>& s) {\n        int cnt_rem_0,cnt_rem_1,cnt_rem_2;\n        cnt_rem_1=cnt_rem_0=cnt_rem_2=0;\n        int n=s.size();\n        for(int i=0;i<n;i++){\n            if(s[i]%3==0)cnt_rem_0++;\n            else if(s[i]%3==1)cnt_rem_1++;\n            else cnt_rem_2++;\n        }\n        if(cnt_rem_1==0 && cnt_rem_2==0){\n            return false;\n        }\n        else{\n            int max_rem_cnt,min_rem_cnt;\n            int ans=0;\n            max_rem_cnt=max(cnt_rem_1,cnt_rem_2);\n            min_rem_cnt=min(cnt_rem_1,cnt_rem_2);\n            \n            if(max_rem_cnt==1){\n              ans= cnt_rem_0+1;\n                if(ans%2==0 || (ans%2==1 && ans==n))return false;\n                else return true;\n            }\n            else{\n                if(min_rem_cnt>=2 && (min_rem_cnt+ min_rem_cnt-1 +cnt_rem_0)%2==1){\n                    return true;\n                }\n                else if(min_rem_cnt==1 && (min_rem_cnt+cnt_rem_0)%2==1 && min_rem_cnt+cnt_rem_0!= n)return true;\n                else{\n                    if(max_rem_cnt==min_rem_cnt){\n                        if( (max_rem_cnt+min_rem_cnt-1+cnt_rem_0)%2==1)return true;\n                        else return false;\n                    }\n                    else if(max_rem_cnt-min_rem_cnt==1){\n                        if((max_rem_cnt+min_rem_cnt+cnt_rem_0)%2==1 && (max_rem_cnt+min_rem_cnt+cnt_rem_0)!=n)return true;\n                        else return false;\n                    }\n                    else{\n                        if((2*min_rem_cnt +2 +cnt_rem_0)%2==1 && (2*min_rem_cnt+2+cnt_rem_0)!=n)return true;\n                        else return false;\n                    }\n                }\n                    \n                }\n            }\n        return true;\n    }\n};\n\n```
[]