Problem statement

https://binarysearch.com/problems/Last-to-Toggle-Wins/

Solution 1

Variation of Leetcode 0294. Flip Game II.

Complexity

It is about O(4^n), but it works pretty fast here.

Code

class Solution:
    def solve(self, arr):
        def moves(state):
            ans, n = [], len(bin(state)) - 2
            for i in range(n - 1):
                if state>>i & 1 and (state >> (i+1)) & 1:
                    ans += [(state + (state&((1<<i) - 1)) - (1<<i) - (1<<(i+1)))>>1]
            return ans
        
        @lru_cache(None)
        def is1Win(state):
            for neib in moves(state):
                if not is1Win(neib): return True
            return False
        
        return is1Win(sum((1<<i)*arr[i] for i in range(len(arr))))

Solution 2

The is also solution, using Sprague-Grundy theorem. We can evaluate MEX values for all value between 0 and n and then evaluate xor in the end of parts.

Complexity

It is O(n^2) for time and O(n) for space.

Code

class Solution:
    def solve(self, arr):
        n = len(arr)
        dp = [0] * (n + 1)  # MEX values
        for i in range(1, n + 1):
            s = set([dp[j] ^ dp[i - 2 - j] for j in range(i - 1)])
            while dp[i] in s: dp[i] += 1

        ans = 0
        for x, y in groupby(arr):
            if x: ans ^= dp[len(list(y))]

        return ans != 0