Approach #1: Mathematical [Accepted]
Intuition and Algorithm
As in the problem statement, if the XOR
of the entire array is 0
, then Alice wins.
If the 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 SpragueGrundy theorem may know that this game is a misèreform game, meaning the theorem does not apply, and giving a big hint that there may exist a simpler solution.
Complexity Analysis

Time Complexity: , where is the length of
nums
. 
Space Complexity: .
Analysis written by: @awice.