Leetcode 1908 Game of Nim

Problem statement

https://leetcode.com/problems/game-of-nim/

Solution

Given problem constraints, it is not difficult to do classical dfs. However the is linear time solution, using Sprague–Grundy theorem: if fact all we need to do is to evaluate XOR of all values.

Complexity

It is O(n) for time and O(1) for space.

Code

class Solution:
    def nimGame(self, piles):
        return reduce(xor, piles) != 0