We build a table of n rows (1-indexed). We start by writing 0 in the 1st row. Now in every subsequent row, we look at the previous row and replace each occurrence of 0 with 01, and each occurrence of 1 with 10.


	For example, for n = 3, the 1st row is 0, the 2nd row is 01, and the 3rd row is 0110.


Given two integer n and k, return the kth (1-indexed) symbol in the nth row of a table of n rows.

&nbsp;
Example 1:

Input: n = 1, k = 1
Output: 0
Explanation: row 1: 0


Example 2:

Input: n = 2, k = 1
Output: 0
Explanation: 
row 1: 0
row 2: 01


Example 3:

Input: n = 2, k = 2
Output: 1
Explanation: 
row 1: 0
row 2: 01


&nbsp;
Constraints:


	1 &lt;= n &lt;= 30
	1 &lt;= k &lt;= 2n - 1


class Solution:
  def solve(self,n,k):
    if n==1 and k==1:
      return 0 
    mid = pow(2,n-1)//2 
    if k<=mid:
      return self.solve(n-1,k) 
    
    return not self.solve(n-1,k-mid)
    
      
  def kthGrammar(self,n,k):
    if self.solve(n,k):
      return 1 
    else:
      return 0 
      
    
   
    
    
    
    
    
    
    
class Solution {
    public int kthGrammar(int n, int k) {
       if (n == 1 || k == 1) {
            return 0;
        }
        int length = (int) Math.pow(2, n - 1);
        int mid = length / 2;
        if (k <= mid) {
            return kthGrammar(n - 1, k);
        } else if (k > mid + 1) {
            return invert(kthGrammar(n - 1, k - mid));
        } else {
            return 1;
        }
    }
    static int invert(int x) {
        if (x == 0) {
            return 1;
        }
        return 0;
    }
}
class Solution {
public:
    int kthGrammar(int n, int k) {
        int kthNode = pow(2, (n-1)) + (k - 1);
        vector<int>arr;
        while(kthNode) {
            arr.push_back(kthNode);
            kthNode /= 2;
        }
        arr[arr.size() - 1] = 0;
        for (int i = arr.size() - 2; i >= 0; i--) {
            if (arr[i] % 2 == 0) {
                arr[i] = arr[i+1];
            }
            else {
                arr[i] = 1 ^ arr[i+1];
            }
        }
        return arr[0];
    }
};
/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var kthGrammar = function(n, k) {
    if (n == 1 && k == 1) {
        return 0;
    }

    const mid = Math.pow(2, n-1) / 2;

    if (k <= mid) {
        return kthGrammar(n-1, k);
    } else {
        return kthGrammar(n-1, k-mid) == 1 ? 0 : 1;
    }
};
K-th Symbol in Grammar