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

<ul>
	<li>For example, for <code>n = 3</code>, the <code>1<sup>st</sup></code> row is <code>0</code>, the <code>2<sup>nd</sup></code> row is <code>01</code>, and the <code>3<sup>rd</sup></code> row is <code>0110</code>.</li>
</ul>

<p>Given two integer <code>n</code> and <code>k</code>, return the <code>k<sup>th</sup></code> (<strong>1-indexed</strong>) symbol in the <code>n<sup>th</sup></code> row of a table of <code>n</code> rows.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 1, k = 1
<strong>Output:</strong> 0
<strong>Explanation:</strong> row 1: <u>0</u>
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 2, k = 1
<strong>Output:</strong> 0
<strong>Explanation:</strong> 
row 1: 0
row 2: <u>0</u>1
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> n = 2, k = 2
<strong>Output:</strong> 1
<strong>Explanation:</strong> 
row 1: 0
row 2: 0<u>1</u>
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 30</code></li>
	<li><code>1 &lt;= k &lt;= 2<sup>n - 1</sup></code></li>
</ul>

class Solution{
public:
    int kthGrammar(int n, int k){
        // Approach: RECURSION + OBSERVATION
        // Self Solved during Random Practice 
        // TC : O(N)
        // SC : O(N) 
        // C++ CODE: 
        // BASE CASE: If we have only 1 row, return the first symbol which is '0' 
        if(n == 1) return 0;

        int length = pow(2, n - 1); // length of the current 'n'th row 
        int mid = length / 2; // mid of the current 'n'th row 

        // If 'k' lies in the first half, then the 'k'th symbol in 'n'th row will be same as 'k'th symbol in the 'n - 1'th row
        // So, ask Recursion to find the 'k'th symbol in the 'n - 1'th row.  
        if(k <= mid) return kthGrammar(n - 1, k);

        // else, if 'k' lies in the 2nd half, then the 'k'th symbol in the 'n'th row will the compliment of 'k - mid'th symbol 
        // in the 'n - 1'th row. Thats why we return the compliment here. 
        else return !kthGrammar(n - 1, (k - mid));
        
        return 0;
    }
};



















/*
class Solution{
public:
    int kthGrammar(int n, int k){
        // Approach 2: RECURSION - IBH (AV)
        // TC : 
        // SC : 
        // C++ CODE:
        // Base Case: If n and k are in the 1st row, return 0
        if(n == 1 && k == 1){
            return 0;
        }
        // Hypothesis: Find the mid of the row, so we need to find the length before
        // int length = 2 to the power (n-1)
        int mid = pow(2, n-1) / 2;
        
        // if 'k' lies in the 1st half, then call the function recursively for n-1th row
        if(k <= mid){
            return kthGrammar(n-1, k); // since if k is in 1st half, kth val of nth row = kth val of n-1 th row
        }
        else{
            // if k lies in the 2nd half, return the compliment (!) of k-mid in n-1 th row
            return !(kthGrammar(n-1, k-mid)); // ! because we need to return the compliment of (k-mid) at n-1 th row
        }
    }
};
*/
7300