Problem statement

https://leetcode.com/problems/chalkboard-xor-game/

Solution

We can notice, that if XOR of all numbers is not equal to 0, there is always turn we can make. Indeed, imagine that we have numbers a1, ..., an and one person removed number ai, such that game is not lost yet. Then other person can also make a move: remove some other number aj, so game is not lost yet. Why there is another number? Because xor of a1, ... an and xor for a1, ... an without ai both not equal to 0 and it is not possible if all numbers are equal.

Complexity

Time complexity is O(n), space complexity is O(1).

Code

class Solution:
    def xorGame(self, nums):
        return reduce(xor, nums) == 0 or len(nums) % 2 == 0