# Find Kth Bit in Nth Binary String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-kth-bit-in-nth-binary-string)
Canonical: https://scaleengineer.com/dsa/problems/find-kth-bit-in-nth-binary-string
**Patterns:** [Recursion](https://scaleengineer.com/dsa/patterns/recursion)
**Data structures:** String
---
## Problem
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 four 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 "**0**111001".
The 1st bit is "0".

**Example 2:**

**Input:** n = 4, k = 11
**Output:** "1"
**Explanation:** S4 is "0111001101**1**0001".
The 11th bit is "1".

**Constraints:**

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

# Approaches
## Brute-force String Construction
This approach directly simulates the process described in the problem. It builds the binary string `S_n` iteratively, starting from `S_1` and applying the given formation rule `n-1` times. Once the full string `S_n` is constructed, it simply retrieves the character at the `k`-th position.
**Time:** O(2^n) - The time taken is dominated by the construction of the final string. The total number of characters generated across all steps is proportional to the sum of lengths of `S_1, S_2, ..., S_n`, which is `O(2^n)`. · **Space:** O(2^n) - We need to store the entire string `S_n`, which has a length of `2^n - 1`.
**Pros:** Simple to understand and implement as it directly follows the problem definition.
**Cons:** Highly inefficient in terms of both time and space complexity.; Not feasible for larger values of `n` (e.g., n > 25) due to exponential growth of the string length.
### Explanation
The brute-force method involves generating the entire binary string `S_n` as defined by the recurrence relation. We start with `S_1 = "0"`. Then, we loop from `i = 2` to `n`, each time generating `S_i` from `S_{i-1}` using the formula `S_i = S_{i-1} + "1" + reverse(invert(S_{i-1}))`. This requires helper functions to perform the `invert` and `reverse` operations. After `n-1` iterations, we will have the complete string `S_n`. The final step is to return the character at the `k-1` index (since `k` is 1-based). Given the constraint `n <= 20`, the maximum length of the string is `2^20 - 1`, which is just over a million characters. Building and storing this string is feasible but computationally expensive.

```java
class Solution {
    public char findKthBit(int n, int k) {
        if (n == 1) {
            return '0';
        }

        StringBuilder s = new StringBuilder("0");

        for (int i = 2; i <= n; i++) {
            StringBuilder inverted = new StringBuilder();
            for (int j = 0; j < s.length(); j++) {
                inverted.append(s.charAt(j) == '0' ? '1' : '0');
            }
            s.append('1').append(inverted.reverse());
        }

        return s.charAt(k - 1);
    }
}
```
### Algorithm
1.  Initialize a string `s` to `"0"`.
2.  Loop from `i = 2` to `n`.
3.  Inside the loop, construct the string for `S_i` based on `S_{i-1}`:
    a.  Create an inverted version of the current string `s`.
    b.  Reverse the inverted string.
    c.  Concatenate the current `s`, the character `"1"`, and the reversed-inverted string to form the new `s`.
4.  After the loop finishes, the string `s` will hold the value of `S_n`.
5.  Return the character at index `k-1` from the final string `s`.

## Recursive Divide and Conquer
Instead of constructing the entire string, this approach uses a divide-and-conquer strategy based on the recursive definition of `S_n`. We can determine the `k`-th bit by figuring out which of the three parts of `S_n` (`S_{n-1}`, the middle `'1'`, or `reverse(invert(S_{n-1}))`) it falls into, and then recursively solving for the smaller subproblem.
**Time:** O(n) - Each recursive call reduces `n` by 1, and the operations within each call are constant time. The total time is proportional to the recursion depth. · **Space:** O(n) - Due to the recursion call stack depth, which can go up to `n`.
**Pros:** Extremely efficient time complexity compared to the brute-force approach.; Avoids the large memory footprint of generating the full string.
**Cons:** Uses recursion, which can lead to stack overflow for very large `n` (though not an issue for the given constraints).; Incurs function call overhead, which can be slightly slower than an equivalent iterative solution.
### Explanation
The key observation is that the string `S_n` has a well-defined structure based on `S_{n-1}`. The length of `S_n` is `2^n - 1`, and its midpoint is at index `mid = 2^(n-1)`. We can find the `k`-th bit without building the string:
- If `k` is exactly `mid`, the bit is `'1'`. 
- If `k` is less than `mid`, the `k`-th bit of `S_n` is the same as the `k`-th bit of `S_{n-1}`. We can make a recursive call for `S_{n-1}` with the same `k`.
- If `k` is greater than `mid`, it falls into the `reverse(invert(S_{n-1}))` part. We can find its corresponding position in `S_{n-1}`, which turns out to be `2^n - k`. The bit at this new position in `S_{n-1}` must be inverted. So, we make a recursive call for `S_{n-1}` with the new `k` and flip the result.
The recursion stops when we reach the base case of `n=1`, where the string is simply `"0"`.

```java
class Solution {
    public char findKthBit(int n, int k) {
        return solve(n, k);
    }

    private char solve(int n, int k) {
        // Base case
        if (n == 1) {
            return '0';
        }

        int mid = 1 << (n - 1); // 2^(n-1)

        if (k == mid) {
            return '1';
        } else if (k < mid) {
            return solve(n - 1, k);
        } else { // k > mid
            char bit = solve(n - 1, 2 * mid - k);
            return (bit == '0') ? '1' : '0';
        }
    }
}
```
### Algorithm
1.  Define a recursive function, let's call it `solve(n, k)`.
2.  **Base Case:** If `n == 1`, the string is `"0"`, so return `'0'`.
3.  Calculate the middle position `mid = 2^(n-1)`.
4.  **Recursive Step:**
    a.  If `k == mid`, the character is the central `'1'`. Return `'1'`.
    b.  If `k < mid`, the character is in the first part (`S_{n-1}`). Recursively call `solve(n - 1, k)`.
    c.  If `k > mid`, the character is in the `reverse(invert(S_{n-1}))` part. The corresponding position in `S_{n-1}` is `2*mid - k`. The bit is the inverse of the bit at that position. Return the result of `!solve(n - 1, 2 * mid - k)`.

## Iterative Approach with Constant Space
This approach optimizes the recursive solution by converting it into an iterative process. It eliminates the recursion stack, reducing space complexity to constant. The logic remains the same: we trace the position `k` down from `S_n` to `S_1`, keeping track of how many times an inversion is needed.
**Time:** O(n) - The loop runs at most `n-1` times, and each iteration performs constant time operations. · **Space:** O(1) - Only a few variables are used to keep track of the state, regardless of the size of `n`.
**Pros:** The most efficient solution with optimal time and space complexity.; Avoids recursion overhead and any risk of stack overflow.
**Cons:** The logic can be slightly less intuitive to derive compared to the direct recursive solution.
### Explanation
We can simulate the recursive calls iteratively. We start with the given `n` and `k` and loop downwards. In each step, we check `k` against the midpoint of the current string `S_n`. If `k` is in the right half, we update `k` to its mirrored position in the left half and increment a `flips` counter. This counter tracks how many times the bit should be inverted. The loop continues until `n` becomes 1 or `k` lands on a midpoint. The final bit is determined by the base bit ('0' for `S_1` or '1' for a midpoint) and the parity of the `flips` counter.

```java
class Solution {
    public char findKthBit(int n, int k) {
        int flips = 0;
        while (n > 1) {
            int mid = 1 << (n - 1);
            if (k == mid) {
                // The original bit is '1'. Apply the flips and return.
                return (flips % 2 == 0) ? '1' : '0';
            }
            if (k > mid) {
                // Mirrored position, requires a flip.
                k = 2 * mid - k;
                flips++;
            }
            // If k < mid, we just move to the next level.
            n--;
        }
        // Base case: n=1, original bit is '0'. Apply flips.
        return (flips % 2 == 0) ? '0' : '1';
    }
}
```
### Algorithm
1.  Initialize a variable `flips = 0` to count the number of inversions.
2.  Start a loop that continues as long as `n > 1`.
3.  In each iteration, calculate the middle position `mid = 2^(n-1)`.
4.  If `k == mid`, the original bit is `'1'`. We can stop and determine the final bit based on the `flips` count.
5.  If `k > mid`, it means we are crossing over to the inverted part. We update `k` to its mirrored position `k = 2 * mid - k` and increment `flips`.
6.  If `k < mid`, we do nothing to `k` or `flips`.
7.  Decrement `n` to move to the next smaller string.
8.  After the loop, the base bit is determined. If the loop was exited because `k == mid`, the base bit is `'1'`. Otherwise, the loop finished, `n` is 1, and the base bit is `'0'`. 
9.  The final result is the base bit if `flips` is even, and the inverted base bit if `flips` is odd.

# Solutions
### Java

```java
class Solution {
public
  char findKthBit(int n, int k) { return (char)('0' + dfs(n, k)); }
private
  int dfs(int n, int k) {
    if (k == 1) {
      return 0;
    }
    if ((k & (k - 1)) == 0) {
      return 1;
    }
    int m = 1 << n;
    if (k * 2 < m - 1) {
      return dfs(n - 1, k);
    }
    return dfs(n - 1, m - k) ^ 1;
  }
}

```

### CPP

```cpp
class Solution {
public:
  char findKthBit(int n, int k) {
    function<int(int, int)> dfs = [&](int n, int k) {
      if (k == 1) {
        return 0;
      }
      if ((k & (k - 1)) == 0) {
        return 1;
      }
      int m = 1 << n;
      if (k * 2 < m - 1) {
        return dfs(n - 1, k);
      }
      return dfs(n - 1, m - k) ^ 1;
    };
    return '0' + dfs(n, k);
  }
};

```

### Python

```python
class Solution:
    def findKthBit(self, n: int, k: int) -> str: def dfs(n: int, k: int) -> int: if k == 1: return 0 if (k & (k - 1)) == 0: return 1 m = 1 << n if k * 2 < m - 1: return dfs(n - 1, k) return dfs(n - 1, m - k) ^ 1 return str(dfs(n, k))

```