Approach #1: Mathematical [Accepted]
Intuition and Algorithm
As in the problem statement, if the
XOR of the entire array is
0, then Alice wins.
XOR condition is never triggered, then clearly Alice wins if and only if there are an even number of elements, as every player always has a move.
Now for the big leap in intuition. Actually, Alice always has a move when there are an even number of elements. If , but there are no possible moves (), then , a contradiction.
Similarly, if there are an odd number of elements, then Bob always faces an even number of elements, and has a move. So the answer is just the parity of the number of elements in the array.
Those that are familiar with the Sprague-Grundy theorem may know that this game is a misère-form game, meaning the theorem does not apply, and giving a big hint that there may exist a simpler solution.
Time Complexity: , where is the length of
Space Complexity: .
Analysis written by: @awice.