779. K-th Symbol in Grammar

LeetCodeの"K-th Symbol in Grammar"
グラフで解けて気持ちよかった。

親子の関係を使って、分割統治法で解ける。計算量もメモリもO(n)。

class Solution(object):
    def kthGrammar(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: int
        """
        if n == 1 and k == 1:
            return 0

        parent = self.kthGrammar(n-1, (k+1)//2)

        if parent == 0:
            if k % 2 == 0:
                return 1
            else:
                return 0
        else:
            if k % 2 == 0:
                return 0
            else:
                return 1