Sponsored
Sponsored
The game can be reduced to a theoretical observation: Alice will win if the XOR of all elements of the array (before any move) is already 0 or if the length of the array is even. This is because, under optimal play, a XOR of 0 or an even number of moves ensures Alice's win. When it's an even number, Bob will be the one forced to make a move that reduces the XOR to 0 if possible.
Time Complexity: O(n), where n is the length of nums.
Space Complexity: O(1), as no extra space is used beyond a few variables.
1function xorGame(nums) {
2 let xorSum = nums.reduce((acc, num) => acc ^ num, 0);
3 return xorSum === 0 || nums.length % 2 === 0;
4}This JavaScript code calculates the XOR of nums using the reduce method. If the XOR is 0 or the length of nums is even, Alice wins under optimal conditions.
This approach builds upon understanding the subproblems of removing each number and calculating the XOR of the remaining elements. Even though its complexity is higher, this method helps us understand more granular moves and outcomes if not assuming mathematical shortcuts.
Time Complexity: O(2^n) due to the exponential number of XOR states possible.
Space Complexity: O(n), largely dictated by function call stack depth.
1using System;
2using System.Collections.Generic;
public class Solution {
private Dictionary<string, bool> memo = new Dictionary<string, bool>();
public bool XorGame(int[] nums) {
int xorSum = 0;
foreach (int num in nums) {
xorSum ^= num;
}
return CanWin(nums, xorSum, 0);
}
private bool CanWin(int[] nums, int xorSum, int mask) {
if (xorSum == 0) return false;
string key = mask + "#" + nums.Length;
if (memo.ContainsKey(key)) return memo[key];
for (int i = 0; i < nums.Length; i++) {
if ((mask & (1 << i)) == 0) {
if (!CanWin(nums, xorSum ^ nums[i], mask | (1 << i))) {
memo[key] = true;
return true;
}
}
}
memo[key] = false;
return false;
}
}The C# approach mirrors the recursive memorization pattern with unique key formation using mask and computations for each player's potential optimal moves.