> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Find Kth Bit in Nth Binary String

> Tested Python solution for LeetCode 1545 with 18 pytest cases. Generate a practice environment with lcpy.

LeetCode 1545, [Medium](/catalog/medium). Topics: [String](/catalog/topics/string), [Recursion](/catalog/topics/recursion), [Simulation](/catalog/topics/simulation). [View on LeetCode](https://leetcode.com/problems/find-kth-bit-in-nth-binary-string/description/).

Generate this problem as a practice environment: tested reference solution, 18 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1545   # by problem number
lcpy gen -s find_kth_bit_in_nth_binary_string   # by problem name
```

## Problem

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

* `S_1 = "0"`
* `S_i = S_i - 1 + "1" + reverse(invert(S_i - 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:

* `S_1 = "0"`
* `S_2 = "011"`
* `S_3 = "0111001"`
* `S_4 = "011100110110001"`

Return *the* `k^th` *bit* *in* `S_n`. It is guaranteed that `k` is valid for the given `n`.

### Examples

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

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

### Constraints

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

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/find_kth_bit_in_nth_binary_string/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/find_kth_bit_in_nth_binary_string/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(log k)
    # Space: O(log k)
    def find_kth_bit(self, n: int, k: int) -> str:
        if k == 1:
            return "0"
        half = 1
        while half * 2 + 1 < k:
            half = half * 2 + 1
        mid = half + 1
        if k == mid:
            return "1"
        mirrored = self.find_kth_bit(n, mid - (k - mid))
        return "0" if mirrored == "1" else "1"
```

## Complexity

| Time | Space |
| - | - |
| O(log k) | O(log k) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.