<h2><a href="https://leetcode.com/problems/find-kth-bit-in-nth-binary-string/">1545. Find Kth Bit in Nth Binary String</a></h2><h3>Medium</h3><hr><div><p>Given two positive integers <code>n</code> and <code>k</code>, the binary string <code>S_n</code> is formed as follows:</p>

<ul>

<li><code>S₁ = "0"</code></li>

<li><code>S_i = S_{i - 1} + "1" + reverse(invert(S_{i - 1}))</code> for <code>i &gt; 1</code></li>

</ul>

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

<p>For example, the first four strings in the above sequence are:</p>

<ul>

<li><code>S₁= "0"</code></li>

<li><code>S₂= "0<strong>1</strong>1"</code></li>

<li><code>S₃= "011<strong>1</strong>001"</code></li>

<li><code>S₄ = "0111001<strong>1</strong>0110001"</code></li>

</ul>

<p>Return <em>the</em> <code>k^th</code> <em>bit</em> <em>in</em> <code>S_n</code>. It is guaranteed that <code>k</code> is valid for the given <code>n</code>.</p>

<p>&nbsp;</p>

<p><strong class="example">Example 1:</strong></p>

<pre><strong>Input:</strong> n = 3, k = 1

<strong>Output:</strong> "0"

<strong>Explanation:</strong> S₃ is "<strong><u>0</u></strong>111001".

The 1^st bit is "0".

</pre>

<p><strong class="example">Example 2:</strong></p>

<pre><strong>Input:</strong> n = 4, k = 11

<strong>Output:</strong> "1"

<strong>Explanation:</strong> S₄ is "0111001101<strong><u>1</u></strong>0001".

The 11^th bit is "1".

</pre>

<p>&nbsp;</p>

<p><strong>Constraints:</strong></p>

<ul>

<li><code>1 &lt;= n &lt;= 20</code></li>

<li><code>1 &lt;= k &lt;= 2ⁿ - 1</code></li>

</ul>

</div>