<p>Given two positive integers <code>n</code> and <code>k</code>, the binary string <code>S<sub>n</sub></code> is formed as follows:</p>

<ul>
	<li><code>S<sub>1</sub> = &quot;0&quot;</code></li>
	<li><code>S<sub>i</sub> = S<sub>i - 1</sub> + &quot;1&quot; + reverse(invert(S<sub>i - 1</sub>))</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<sub>1 </sub>= &quot;0&quot;</code></li>
	<li><code>S<sub>2 </sub>= &quot;0<strong>1</strong>1&quot;</code></li>
	<li><code>S<sub>3 </sub>= &quot;011<strong>1</strong>001&quot;</code></li>
	<li><code>S<sub>4</sub> = &quot;0111001<strong>1</strong>0110001&quot;</code></li>
</ul>

<p>Return <em>the</em> <code>k<sup>th</sup></code> <em>bit</em> <em>in</em> <code>S<sub>n</sub></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> &quot;0&quot;
<strong>Explanation:</strong> S<sub>3</sub> is &quot;<strong><u>0</u></strong>111001&quot;.
The 1<sup>st</sup> bit is &quot;0&quot;.
</pre>

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

<pre>
<strong>Input:</strong> n = 4, k = 11
<strong>Output:</strong> &quot;1&quot;
<strong>Explanation:</strong> S<sub>4</sub> is &quot;0111001101<strong><u>1</u></strong>0001&quot;.
The 11<sup>th</sup> bit is &quot;1&quot;.
</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<sup>n</sup> - 1</code></li>
</ul>

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        string = ""
        for i in range(n):
            if i == 0:
                string += "0"
            else:
                inverted = ""
                for i in range(len(string)):
                    if string[i] == "0":
                        inverted += "1"
                    else:
                        inverted += "0"
                string = string + "1" + inverted[::-1]
        
        return string[k-1]


class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        # Divide and Conquer:
        # If k is in the first half of Sn, it corresponds directly to the same position in Si-1.
        # If k is the middle bit (which is 2^(n-1)), it is always 1.
        # If k is in the second half, it corresponds to the inverse of the bit at the mirrored position in the first half of Si-1.
        if n == 1:
            return "0"
        
        # Calculate the length of Sn-1: length_of_Sn_minus_1 = 2^(n-1) - 1
        length_of_Sn_minus_1 = (2 ** (n - 1)) - 1
        middle_index = length_of_Sn_minus_1 + 1  # middle index in Sn
        
        if k == middle_index:
            return "1"
        elif k < middle_index:
            return self.findKthBit(n - 1, k)
        else:
            # Calculate the mirrored position in the first half
            mirrored_position = 2 * length_of_Sn_minus_1 + 2 - k
            return '1' if self.findKthBit(n - 1, mirrored_position) == '0' else '0'




class Solution:
    def findKthBit(self, n: int, k: int) -> str:

        # this function assumes 1-indexed, that is 1 is starting idx and 7 is 7th idx if len=7
        def findKthBitInt(n: int, k: int) -> int:
            # base case 
            if n == 1:
                return 0
            
            # calculate length of Sn
            l = 2**n - 1

            # center case: k is exactly the middle
            center = (l + 1) / 2
            if k == center:
                return 1

            # recursive case: k is in first half (not center)
            if k <= (l // 2):
                return findKthBitInt(n - 1, k)

            # other half case: k is in the second half (not center)
            return 1 - findKthBitInt(n - 1, l - k + 1)
        
        return str(findKthBitInt(n, k))



class Solution:
    def findKthBit(self, n: int, k: int) -> str:

        def findKthBitInt(n,k):
            if n == 1:
                return 0
            length = 2 ** n - 1
            middle = (length // 2) + 1

            if k == middle:
                return 1
            elif k <= length // 2:
                return findKthBitInt(n-1,k)
            else:
                # as invert + reverse, so if k = 5 and n = 3, then considering 1-indexed, then new k = 7 - 5 + 1
                # as s3 = 0111001 and s2 = 001, so s3[5] = s2[3] as invert + reverse
                return 1 - findKthBitInt(n-1,length-k+1)
        
        return str(findKthBitInt(n,k))



class Solution:
    def findKthBit(self, n: int, k: int) -> str:

        def findKthBitInt(n,k):
            if n == 1:
                return 0
            
            length = (2 ** n) - 1
            mid = (length // 2) + 1
            if mid == k:
                return 1
            elif k < mid:
                return findKthBitInt(n-1,k)
            else:
                return 1 - findKthBitInt(n-1,length-k+1)
        
        return str(findKthBitInt(n,k))
16700