779. K-th Symbol in Grammar

Recursive

Consideration

• Length is 2**n
• The kth bit is:
  • Same with the kth bit in the n-1 level if k <= 2**(n-1)
  • Inverse with kth bit in the n-1 level if k > 2**(n-1)

Examples

Consider (n, k) as (5, 10), then:

(5, 10) => !(4, 2) => (3, 2) => (2, 2) => !(1,1)

n	bits
1	0
2	01
3	0110
4	01101001
5	0110100110010110

Python

• O(n)

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        if n == 1:
            return 0

        half_length = 2 ** (n-2)
        if k > half_length:
            # k in the right, invert with previous level
            return 1 if self.kthGrammar(n-1, k-half_length) == 0 else 0

        # k in the left, same with previous level
        return self.kthGrammar(n-1, k)

Brute Solution (Fail Try)

• O(n^2 + k)
• Timelimit exceed

Python

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        if n == 1:
            if k > 1:
                return
            else:
                return 0

        return self._travel(2, n, k, [0])

    def _travel(self, cur_n, target_n, k, pre):
        if cur_n > target_n:
            return pre.pop(k-1)

        nums = []
        limit = k/2
        for num in pre:
            if limit < 0:
                break
            if num == 0:
                nums.append(0)
                nums.append(1)
            else:
                nums.append(1)
                nums.append(0)
            limit -= 1

        return self._travel(cur_n+1, target_n, k, nums)