Leetcode 795 Solution

This article provides solution to leetcode question 795 (k-th-symbol-in-grammar)
Categories:
Tags:
Access this page by simply typing in "lcs 795" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/k-th-symbol-in-grammar

Solution

class Solution:
    def kthGrammar(self, N: int, K: int) -> int:
        def dfs(N, K, val):
            if N == 1:
                return val

            if K <= 2 ** (N - 2):
                return dfs(N - 1, K, val)
            else:
                return dfs(N - 1, K - 2 ** (N - 2), 1 - val)

        return dfs(N, K, 0)