Leetcode 2005 Subtree Removal Game with Fibonacci Tree

Problem statement

https://leetcode.com/problems/subtree-removal-game-with-fibonacci-tree/

Solution

It is quite a difficult problem, where you need to know some theorems from game theory. It is connected with Sprague-Grundy value of game. Actually the considered game is the special case of Hackenbush game, which can be solved with Colon principle. The idea can be viewed as symmetric strategy in some sense, but at the moment I do not fully investigated it. Moreover it can be proved that return n % 6 != 1 is correct, it can be proved by induction.

Complexity

It is O(n) for time and space. Space can be reduced to O(1).

Code

class Solution:
    def findGameWinner(self, n):
        @lru_cache(None)
        def sg(i):
            if i <= 2: return i - 1
            return (sg(i-1) + 1) ^ (sg(i-2) + 1)
        
        return sg(n) != 0