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 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.

Complexity Analysis

  • Time Complexity: , where is the length of nums.

  • Space Complexity: .

Analysis written by: @awice.