# 779. K-th Symbol in Grammar

## Problem Statement

<br>

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.

&#x20;

**Example 1:**

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

**Example 2:**

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

**Example 3:**

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

&#x20;

**Constraints:**

* `1 <= n <= 30`
* `1 <= k <= 2n - 1`

## Intuition

```
Approach:
1->0
2->0|1
3->01|10
4->0110|1001

See that bits are flipped, after some time

Try recursion to find that 

```

### Links

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

### Video Links

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    unordered_map<string,int> mp;
    int find_ans(int n, int k){
        if(n == 1 and k == 1)
            return 0;
        
        string key = to_string(n) + "_" + to_string(k);
        if(mp.find(key) != mp.end())
            return mp[key];

        int dist = pow(2,n-2) + 1;

        if(k < dist)
            return mp[key] = find_ans(n-1, k);
        
        return mp[key] = 1 ^ find_ans(n, k-dist+1);
    }

    int kthGrammar(int n, int k) {
        int ans = find_ans(n, k);
        for(auto &it: mp){
            cout<<it.first <<" "<<it.second;
            cout<<endl;
        }
        return ans;
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###