# K-th Symbol in Grammar
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/k-th-symbol-in-grammar)
Canonical: https://scaleengineer.com/dsa/problems/k-th-symbol-in-grammar
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Recursion](https://scaleengineer.com/dsa/patterns/recursion), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
---
## Problem
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.

**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

**Constraints:**

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

# Approaches
## Brute Force Simulation
This approach directly simulates the process described in the problem. We start with the string for the first row, "0", and iteratively generate the string for each subsequent row up to `n`. This method is straightforward but computationally expensive.
**Time:** O(2^n). The length of the string for row `i` is `2^(i-1)`. Building the string for row `i` takes O(2^(i-1)) time. The total time is the sum of these lengths, which is dominated by the final step, resulting in O(2^n) complexity. · **Space:** O(2^n). We need to store the string for the `n`-th row, which has a length of `2^(n-1)`. This is infeasible for `n=30`.
**Pros:** Simple to understand and directly follows the problem statement.
**Cons:** Highly inefficient for the given constraints (`n <= 30`).; Will result in Time Limit Exceeded (TLE) and Memory Limit Exceeded (MLE) on most platforms.
### Explanation
The algorithm begins with the base case, row 1, which is simply "0". It then enters a loop that runs from row 2 to row `n`. In each iteration, it constructs the next row by scanning the current row. For every '0' encountered, it appends "01" to a new string builder, and for every '1', it appends "10". After the new row is fully constructed, it replaces the old row. This process continues until the `n`-th row is generated. Finally, it retrieves the character at the `k-1`-th index (since `k` is 1-indexed) and converts it to an integer to get the final answer.

```java
class Solution {
    public int kthGrammar(int n, int k) {
        String currentRow = "0";
        for (int i = 2; i <= n; i++) {
            StringBuilder nextRow = new StringBuilder();
            // The length of the string can become very large, so we might not even
            // be able to build it for large n. This code is for demonstration.
            for (char c : currentRow.toCharArray()) {
                if (c == '0') {
                    nextRow.append("01");
                } else {
                    nextRow.append("10");
                }
            }
            currentRow = nextRow.toString();
        }
        return currentRow.charAt(k - 1) - '0';
    }
}
```
### Algorithm
- Initialize a string `currentRow` to "0".
- Loop from `i = 2` to `n`.
- Inside the loop, create a `StringBuilder` for the next row.
- Iterate through each character of `currentRow`.
- If the character is '0', append "01" to the `StringBuilder`.
- If the character is '1', append "10" to the `StringBuilder`.
- After iterating, update `currentRow` to the string from the `StringBuilder`.
- After the main loop finishes, `currentRow` holds the string for the `n`-th row.
- The result is the character at index `k-1`. Convert the character '0' or '1' to an integer.

## Recursive Approach
This approach leverages the self-similar structure of the grammar. We can observe that the `n`-th row is formed by taking the `(n-1)`-th row and appending its bitwise complement. This allows us to find the `k`-th symbol without constructing the full row by recursively determining its value from the previous row.
**Time:** O(n). In each recursive call, `n` is decremented by 1. The recursion depth is `n`, and each call involves a constant number of operations. · **Space:** O(n). This is due to the recursion call stack depth, which can go up to `n`.
**Pros:** Significantly more efficient than brute force and feasible for the given constraints.; The logic is intuitive once the fractal-like pattern is identified.
**Cons:** The recursive calls consume stack space, which could be a concern for extremely large `n` (though not an issue with `n <= 30`).
### Explanation
The key observation is that for any row `n > 1`, the first half of the row is identical to row `n-1`, and the second half is the bitwise complement (0s become 1s, 1s become 0s) of row `n-1`. The length of row `n` is `2^(n-1)`, so the midpoint is at index `2^(n-2)`. Based on this, we can determine the value of the `k`-th symbol. If `k` lies in the first half, its value is the same as the `k`-th symbol in row `n-1`. If `k` lies in the second half, its value is the complement of the `(k - midpoint)`-th symbol in row `n-1`. This logic forms a recursive relation that bottoms out at `n=1`, where the value is always 0.

```java
class Solution {
    public int kthGrammar(int n, int k) {
        // Base case: The first row is just "0".
        if (n == 1) {
            return 0;
        }

        // Length of the previous row (n-1).
        int prevRowLength = 1 << (n - 2); // Equivalent to 2^(n-2)

        // If k is in the first half of the current row.
        if (k <= prevRowLength) {
            // The value is the same as in the previous row.
            return kthGrammar(n - 1, k);
        } else {
            // If k is in the second half, the value is the complement
            // of the corresponding element in the previous row.
            // The corresponding position is k - prevRowLength.
            return 1 - kthGrammar(n - 1, k - prevRowLength);
        }
    }
}
```
### Algorithm
- Define a recursive function, say `solve(row, index)`.
- **Base Case:** If `row == 1`, the only symbol is 0. Return 0.
- Calculate the length of the previous row, `prevRowLength = 2^(row - 2)`.
- **Recursive Step:**
  - If `index` is in the first half (i.e., `index <= prevRowLength`), the symbol is the same as the symbol at `index` in the previous row. We make a recursive call: `solve(row - 1, index)`.
  - If `index` is in the second half (i.e., `index > prevRowLength`), the symbol is the complement of the corresponding symbol in the previous row. The corresponding index in the previous row is `index - prevRowLength`. We make a recursive call `solve(row - 1, index - prevRowLength)` and return its complement (`1 - result`).

## Bit Manipulation
This is the most optimal approach, derived from a deeper analysis of the recursive pattern. It connects the problem to the binary representation of `k-1` and finds the answer in constant time. The value of the `k`-th symbol is simply the parity of the number of set bits in `k-1`.
**Time:** O(1). The `Integer.bitCount` operation is highly optimized and often translates to a single CPU instruction, making it effectively constant time for a fixed-size integer (like a 32-bit or 64-bit int). · **Space:** O(1). No extra space is used besides a few variables.
**Pros:** Extremely efficient in both time and space.; The solution is very concise and elegant.
**Cons:** The underlying logic is less intuitive than the recursive approach and requires a mathematical insight into the pattern.
### Explanation
Let's analyze the parent-child relationship using 0-indexed `k`. The `k`-th symbol in row `n`, `S_n[k]`, is generated from the `floor(k/2)`-th symbol in row `n-1`. The generation rule `0 -> 01` and `1 -> 10` can be expressed as `S_n[k] = S_{n-1}[floor(k/2)] XOR (k % 2)`. By expanding this recurrence relation down to the base case `S_1[0] = 0`, we find that `S_n[k]` is the XOR sum of all the bits in the binary representation of `k`. The XOR sum of bits is 1 if the number of set bits (popcount) is odd, and 0 if it is even. Therefore, for a 1-indexed `k` from the problem, the symbol is `popcount(k-1) % 2`.

```java
class Solution {
    public int kthGrammar(int n, int k) {
        // The problem is equivalent to finding the parity of the number of set bits
        // in the binary representation of k-1.
        // If the count of 1s is even, the result is 0.
        // If the count of 1s is odd, the result is 1.
        // This is the same as Integer.bitCount(k - 1) % 2.
        return Integer.bitCount(k - 1) % 2;
    }
}
```
### Algorithm
- The problem asks for the `k`-th symbol (1-indexed). We will work with `k-1` (0-indexed).
- The core insight is that the value of the symbol at a given position is determined by the parity of the number of set bits in its 0-indexed position.
- Calculate `k-1`.
- Count the number of set bits (1s) in the binary representation of `k-1`. Most languages provide a built-in function for this (e.g., `Integer.bitCount()` in Java).
- Find the parity of this count. If the count is even, the result is 0. If the count is odd, the result is 1. This is equivalent to `count % 2`.

# Solutions
### Java

```java
class Solution {
public
  int kthGrammar(int n, int k) { return Integer.bitCount(k - 1) & 1; }
}

```

### CPP

```cpp
class Solution {
public:
  int kthGrammar(int n, int k) { return __builtin_popcount(k - 1) & 1; }
};

```

### Python

```python
class Solution:
    def kthGrammar(self, n: int, k: int) -> int: return (k -
                                                         1). bit_count() & 1

```