Problem Description
Given an array of integers where each represents a number written on a chalkboard, two players (Alice and Bob) take turns erasing exactly one number from the array. Erasing a number that causes the bitwise XOR of all remaining elements to become 0 results in an immediate loss for that player. Additionally, if a player's turn begins with the board’s XOR already 0, that player wins immediately. Assuming both players play optimally, determine whether Alice wins the game.
Key Insights
- The overall XOR of the array is the key factor in determining the outcome.
- If the XOR of the entire board is 0 at the start, then Alice wins immediately.
- If the XOR is non-zero:
- When the array contains an even number of elements, Alice can always mirror Bob’s moves and win.
- When the array contains an odd number of elements, Bob can force a win with optimal play.
- The solution is based on the observation that if XOR(nums) != 0 and the array length is odd, then Alice cannot avoid leaving a winning position for Bob.
Space and Time Complexity
Time Complexity: O(n), where n is the number of elements in the array (for computing the XOR). Space Complexity: O(1) (no additional space is used beyond a few variables).
Solution
The solution first computes the XOR of all the elements in the array. If the result is 0, Alice wins immediately. Otherwise, the only situation where Alice can win is when the number of elements (i.e., the number of moves) is even, which allows her to mimic Bob’s move and eventually force him into a losing position. This approach leverages game theory and the properties of XOR.