> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/bit-manipulation/find-kth-bit-in-nth-binary-string.md).

# Find Kth Bit in Nth Binary String

Given two positive integers `n` and `k`, the binary string  `Sn` is formed as follows:

* `S1 = "0"`
* `Si = Si-1 + "1" + reverse(invert(Si-1))` for `i > 1`

Where `+` denotes the concatenation operation, `reverse(x)` returns the reversed string x, and `invert(x)` inverts all the bits in x (0 changes to 1 and 1 changes to 0).

For example, the first 4 strings in the above sequence are:

* `S1 = "0"`
* `S2 = "0`**`1`**`1"`
* `S3 = "011`**`1`**`001"`
* `S4 = "0111001`**`1`**`0110001"`

Return *the* `kth` *bit* *in* `Sn`. It is guaranteed that `k` is valid for the given `n`.

**Example 1:**

```
Input: n = 3, k = 1
Output: "0"
Explanation: S3 is "0111001". The first bit is "0".
```

**Example 2:**

```
Input: n = 4, k = 11
Output: "1"
Explanation: S4 is "011100110110001". The 11th bit is "1".
```

**Example 3:**

```
Input: n = 1, k = 1
Output: "0"
```

**Example 4:**

```
Input: n = 2, k = 3
Output: "1"
```

**Constraints:**

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

```java
class Solution {
    public char findKthBit(int n, int k) {
        if (n == 1)
            return '0';
        // Calculate length of Sn (2^n - 1)
        int len = (1 << n) - 1;
        int mid = (len / 2) + 1;
        // The middle will always be '1', because of how we create Sn
        if (k == mid)
            return '1';
        else if (k < mid)
            return findKthBit(n - 1, k);
        else
            // Find the answer received from 2nd part, because 2nd part is created
            // by flipping and inverting
            return findKthBit(n - 1, len - k + 1) == '0' ? '1' : '0';
    }
}
```