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 = "011"
S3 = "0111001"
S4 = "011100110110001"

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

Difficulty: interview

Starter code:

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

Solutions:
class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        i = n - 1
        invert = False
        while i > 0:
            half_len = (2**(i + 1) - 1) // 2 
            if k == half_len + 1:
                return '1' if not invert else '0'
            
            if k > half_len:
                k = half_len - (k - half_len - 1) + 1
                invert = not invert
            i -= 1
        
        return '1' if invert else '0'

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        # S的奇数序列是 01010101，(3, 7, 11, ...)是1
        # 所以如果k是奇数，直接返回 (k >> 1) & 1
        
        # S的偶数序列是 1101100... (2, 4, 6, 8, 10, ...)
        # 这个序列的奇数序列是 10101010，(2, 6, 10, 14, ...), (2, 10, 18, ...)是1
        # 所以如果k是偶数，k >> 1就将偶数序列移动到奇数位置上 -> (1, 5, 9, ...)是1
        # 重复这个过程直到k为奇数，然后 (k >> 1) & 1 ^ 1
        
        # k // (k & -k) 相当于除到k为奇数。
        return str((k // (k & -k)) >> 1 & 1 ^ ((k & 1) ^ 1))
    
    def findKthBit_logn(self, n: int, k: int) -> str:
        cur, flip = 1 << (n - 1), 0
        while k > 1:
            if k & (k - 1) == 0:
                return str(flip ^ 1)
            if k > cur:
                k = 2 * cur - k
                flip ^= 1
            cur >>= 1
        
        return str(flip)

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        dp = [[]] * n
        dp[0] = [0]
        for i in range(1, n):
            dp[i] = dp[i - 1] + [1] +list(reversed([v ^ 1 for v in dp[i - 1]]))
        return str(dp[-1][k - 1])

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        
        def invert(s): return ''.join(['1' if c=='0' else '0' for c in s])
        def revStr(s): return ''.join(list(reversed(s)))
        
        counter = 1
        x = '0'
        while counter!=n:
            # make new string, increment counter
            x = x + '1' + revStr(invert(x))
            counter += 1
        
        return x[k-1]


def reverse(m):
        t=''
        for i in m:
            if i=='1':
                t=t+'0'
            else:
                t=t+'1'
        return t  
class Solution:      
    def findKthBit(self, n: int, k: int) -> str:
        s='0';
        while(n>1):
            t=reverse(s)
            s=s+'1'+t[::-1]
            n-=1;
        return s[k-1];

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        return self.solv(n, k)
    
    def solv(sef, n, k):
        i = 1
        lst = ['0']
        ans = '0'
        ki = 1
        if k == 1:
            return '0'
        while i < n+1:
            ans = '1'
            lst.append(ans)
            ki += 1
            if ki == k:
                return ans
            for j in range(ki-2,-1,-1):
                ans = '1' if lst[j] == '0' else '0'
                lst.append(ans)
                ki += 1
                if ki == k:
                    return ans
            i += 1
        return None

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        full = [0]

        for _ in range(n - 1):
            full = full + [1] + [(x + 1) % 2 for x in full][::-1]
        
        return str(full[k - 1])


class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        l = [0]*(n+1)
        for i in range(1,n+1):
            l[i] = 2*l[i-1]+1
        # print(l)
        def helper(n,k,f):
            m = l[n]
            # print(m,k,f)
            if n == 1: return 0^f
            if k == m//2+1: return 1^f
            if k <= m//2:
                return helper(n-1,k,f)
            else:
                return helper(n-1,m-k+1,1^f)

        return str(helper(n,k,0))

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

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        # First element is for n == 1
        cache = [''] * n

        def gen_str(n):
            if n-1 in cache:
                return cache[n-1]

            if n == 1:
                s = '0'
                cache[0] = s
                return s

            prev = gen_str(n-1)
            s = prev + '1'
            for c in reversed(prev):
                if c == '0':
                    s += '1'
                else:
                    s += '0'
            cache[n-1] = s
            return s

        return gen_str(n)[k-1]

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        def invert(data):
            ans = ''
            for val in data:
                if val == '1':
                    ans += '0'
                else:
                    ans += '1'
            return ans
        
        res = [''] * (n+1)
        res [1] = '0'
        for i in range(2, n+1):
            res[i] = res[i-1] + '1' + invert(res[i-1])[::-1]
            
        return res[n][k-1]


class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        s = '0'
        while n > 1:
            p = ''
            for l in s[::-1]:
                p += '1' if l == '0' else '0'
            s = s + '1' + p
            n -= 1
        return s[k - 1]

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        dp = [None]*(n)
        dp[0] = '0'
        for i in range(1, n):
            m = ''
            inv = self.invert(dp[i-1],m)
            rev = self.reverse(inv)
            dp[i] = dp[i-1]+'1'+rev
        return dp[-1][k-1]
        
    def reverse(self, string):
        return string[::-1]
    def invert(self, string,m):
        for i in range(len(string)):
            if string[i]=='1':
                m+='0'
            else:
                m+='1'
        return m

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        def invert(data):
            ans = ''
            for val in data:
                if val == '1':
                    ans += '0'
                else:
                    ans += '1'
            return ans
        
        res = [''] * (n+1)
        res [1] = '0'
        for i in range(2, n+1):
            res[i] = res[i-1] + '1' + invert(res[i-1])[::-1]
        
        return res[n][k-1]


class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        
        def invert(s):
            inv=''
            for ch in s:
                inv+='0' if ch=='1' else '1'
            return inv
        s='0'
        for i in range(1,n):          
            s=s+'1'+invert(s)[::-1]
            
        return s[k-1]


class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        if n==1:
            return '0'
        def rev(s):
            return s[::-1]
        def invert(r):
            t=''
            for i in r:
                if i=='1':
                    t+='0'
                else:
                    t+='1'
            return t
        z='0'
        for i in range(2,n+1):
            a=invert(z)
            b=rev(a)
            z+='1'+b
        return z[k-1]
            
            


class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        s=[]
        s.append('0')
        for i in range(1,n):
            ans=s[i-1]+'1'
            temp=''
            for j in s[i-1]:
                if j=='0':
                    temp+='1'
                else:
                    temp+='0'
            ans=ans+temp[::-1]
            s.append(ans)
        return s[-1][k-1]

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        def reverse(cur_s):
            return ''.join([c for c in reversed(cur_s)])
        
        def invert(cur_s):
            return ''.join(['1' if c == '0' else '0' for c in cur_s])
            
        S = '0'
        for i in range(1, n):
            S += '1' + reverse(invert(S))
        
        return S[k-1]

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        x = '0'
        for i in range(1, n):
            x = x + '1' + ''.join(list(map(lambda x: '1' if x == '0' else '0', x))[::-1])
        return x[k-1]

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        
        series = ['0']
        for i in range(n-1):
            series = self.getNext(series)
            #print(series)
        return series[k-1]
        
    def getNext(self, series):
        
        extension = series[::-1]
        for idx, c in enumerate(extension):
            if c == '0':
                extension[idx] = '1'
            else:
                extension[idx] = '0'
        return series + ['1'] + extension                

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        s = '0'
        for i in range(1, n):
            chars = []
            for j in reversed(list(range(len(s)))):
                chars.append('1' if s[j] == '0' else '0')
            s += '1' + ''.join(chars)
            # print('i = {0}, s = {1}'.format(i, s))
        return s[k - 1]


def invert(s):
    return (bin(int(s, 2)^int('1'*len(s), 2)))[2:]

def reverse(s):
    return s[::-1]

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        S = [None]*n
        S[0] = '0'
        for i in range(1, n):
            S[i] = S[i-1] + '1' + reverse(invert(S[i-1]))
        
        return S[n-1][k-1]

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        s='0'
        for i in range(1,n):
            inv=''
            for j in s:
                if j=='1':
                    inv+='0'
                else:
                    inv+='1'
            s=s+'1'+inv[::-1]
        return s[k-1]


class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        bits = [False]
        
        for i in range(1, n+1):
            bits.extend([True] + [j==False for j in bits[::-1]])
            
        return str(int(bits[k-1]))

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        def invert(s):
            temp = ''
            for i in range(len(s)):
                if(s[i]=='1'):
                    temp = temp + '0'
                else:
                    temp = temp+'1'
            return temp
        
        s = '0'
        for i in range(1,n):
            inv = invert(s)
            rev = inv[::-1]
            s = s + '1' + rev
            
        return s[k-1]
            


# 10th finish 14:18

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        s = ['0']
        for i in range(n-1):
            temp1 = s.copy()
            for i in range(len(temp1)):
                if temp1[i] == '0':
                    temp1[i] = '1'
                elif temp1[i] == '1':
                    temp1[i] = '0'
            temp1.reverse()
            temp = s + ['1'] + temp1
            s = temp
        # print(s)
        return s[k-1]

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        def reverse_invert(array: List[str]) -> List[str]:
            res = []
            for ind in range(len(array)-1, -1, -1):
                res.append('1' if array[ind] == '0' else '0')
            return res
        
        bits = ['0']
        for curr in range(2, n+1):
            bits += ['1'] + reverse_invert(bits)
        return bits[k-1]

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        def negVal(val):
            lenVal = len(val)
            mask = int(('1' * lenVal), 2)
            val = int(val, 2)
            neg = (val ^ mask)
            lenNeg = len(bin(neg)) - 2
            neg = '0' * (lenVal - lenNeg) + bin(neg)[2:]
            return neg[::-1]
            
        strVal = '0'
        for i in range(n - 1):
            strVal += '1' + negVal(strVal)
            
        if(k > len(strVal)):
            return '0'
        else:
            return strVal[k - 1]

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        s = ['0']
        for i in range(n-1):
            temp1 = s.copy()
            for i in range(len(temp1)):
                if temp1[i] == '0':
                    temp1[i] = '1'
                elif temp1[i] == '1':
                    temp1[i] = '0'
            temp1.reverse()
            temp = s + ['1'] + temp1
            s = temp
        # print(s)
        return s[k-1]

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        def invert(bin):
            bin = list(bin)
            for i in range(len(bin)):
                if bin[i] == '1': 
                    bin[i] = '0'
                else:
                    bin[i] = '1'
            return ''.join(bin)
        bin_n = bin(n)[2:]
        dp = ['0'] * n
        for i in range(1,n):
            dp[i]  = dp[i-1] + '1' + invert(dp[i-1])[::-1]
        return dp[-1][k-1]


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

        d = dict()
        d[0] = [0]
        for i in range(1, n+1):
            d[i] = d[i-1] + [1] + [1-x for x in d[i-1]][::-1]

        return str(d[n][k-1])

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        sn = ['0']
        for i in range(1, n):
            nx = sn[i-1] + '1' + self.reverse(self.invert(sn[i-1]))
            sn.append(nx)
        return sn[-1][k-1]
    
    def invert(self, s):
        return ''.join('0' if _ == '1' else '1' for _ in s)
    
    def reverse(self, s):
        return ''.join(reversed(s))

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        
        def invert(n):
            s = ''
            #print('ss', n)
            for char in n:
                if char == '0':
                    s += '1'
                else:
                    s += '0'
            return s
                
        def generater(n):
            dp = [-1]*n
            dp[0] = '0'
            for i in range(1, len(dp)):
                #print(i, dp)
                dp[i] = dp[i-1] + '1' + invert(dp[i-1])[::-1]
            return dp[-1]
        #print(generater(3))
        return generater(n)[k-1]

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        
        s = ['0']
        for _ in range(n-1):
            s += ['1'] + [('1','0')[int(x)] for x in reversed(s)]
        return s[k-1]


class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        
        s = ['0']
        for _ in range(n-1):
            s += ['1'] + list(reversed([('1','0')[int(x)] for x in s]))
        return s[k-1]


import math
class Solution:
    def findKthBit(self, j: int, k: int) -> str:
        n=j
        lst=['0']
        
        for i in range(n):
            lst=lst+['1']+ ['1' if ele=='0' else '0' for ele in lst[::-1]]
            
        return lst[k-1]

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

    s = '0'
    i = 0
    while i < n:
      inverted = ''.join('1' if c == '0' else '0' for c in s)[::-1]
      s = s + '1' + inverted
      i+=1

    return s[k]

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        
        memo_table = [ '' ] * (n)
        
        memo_table[0] = '0'
        
        for i in range(1, n):
            memo_table[i] = self.new_level(memo_table[i-1])
        
        return memo_table[n-1][k-1]
    
    def new_level(self, old_level: str):
        new_level = [ '1' ] * (len(old_level) * 2 + 1)
        left = 0
        right = len(old_level)*2
        for c in old_level:
            new_level[left] = c
            if c == '0':
                new_level[right] = '1'
            else:
                new_level[right] = '0'
            left += 1
            right -= 1
        
        return ''.join(new_level)
            
            


class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        def revert(s):
            ans = ''
            for x in s:
                if x == '1':
                    ans += '0'
                else:
                    ans += '1'
            return ans
        def helper(n):
            if n == 1:
                return '0'
            res = helper(n - 1)
            return res + '1' + revert(res)[::-1]
        return helper(n)[k-1]

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        from copy import deepcopy
        
        
        @lru_cache()
        def help(i):
            if i==1:
                return '0'
            
            s=help(i-1)
            s2=deepcopy(s)
            v=[]
            for i in s:
                v.append(i)
                
            for i in range(len(v)):
                if v[i]=='1':
                    v[i]='0'
                    
                else:
                    v[i]='1'
                    
            v=v[::-1]
            s=''.join(v)
            return s2+'1'+s
        
        
        return help(n)[k-1]

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        
        def revert(s):
            ans = ''
            for x in s:
                if x == '1':
                    ans += '0'
                else:
                    ans += '1'
            return ans
        
        def helper(n):
            if n == 1:
                return '0'
            res = helper(n - 1)
            return res + '1' + revert(res)[::-1]
        return helper(n)[k - 1]

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        
        def reverseInvert(string: str) -> str:
            output = []
            for char in string:
                if char == '0':
                    output.append('1')
                else:
                    output.append('0')
            output.reverse()
            return ''.join(output)
            
        def getNthSequence(n: int) -> str:
            if n == 1:
                return '0'
            prev = getNthSequence(n-1)
            return prev + '1' + reverseInvert(prev)
        
        return getNthSequence(int(ceil(log2(k)) + 1))[k-1]


class Solution:
    
    def invert(self, s):
        out = ''
        for c in s:
            if c == '0':
                out += '1'
            if c == '1':
                out += '0'
        return out
    
    def reverse(self, s):
        return s[::-1]
    
    def findKthBit(self, n: int, k: int) -> str:
        l = []
        for i in range(n):
            if i == 0:
                l.append('0')
            else:
                last_s = l[-1]
                s = last_s + '1' + self.reverse(self.invert(last_s))
                l.append(s)
        s = l[-1]
        return s[k-1]


class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        def inverse(s):
            res = ''
            for ch in s:
                if ch == '1':
                    res += '0'
                else:
                    res += '1'
            return res
        
        
        s = '0'
        for i in range(n-1):
            s = s+'1' + inverse(s)[::-1]
        return s[k-1]

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        
        s0='0'
        
        i=1
        while i<=n:
            s0=s0+'1'+self.reverse(s0)
            i=i+1
       
        return s0[k-1]
        
        
    def reverse(self,s):
        mapp={'1':'0','0':'1'}
        ans=''
        for x in s:
            ans=ans+mapp[x]
            
        return ans[::-1]
            
        
            


class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        def invert(data):
            ans = ''
            for val in data:
                if val == '1':
                    ans += '0'
                else:
                    ans += '1'
            return ans

        res = '0'
        for _ in range(n):
            res += '1' + invert(res)[::-1]

        return res[k - 1]


class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        def inv(s):
            n = ''
            for i in s:
                if i=='1':
                    n+='0'
                else:
                    n+='1'
            return n
        def rev(s):
            return s[::-1]
        
        s='0'
        for i in range(n):
            s=s+'1'+rev(inv(s))
        return s[k-1]


class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        def reverse(s):
            return ''.join([s[len(s) - 1 - i] for i in range(len(s))])
            
        def invert(s):
            return ''.join(['1' if s[i] == '0' else '0' for i in range(len(s))])
            
        def findNthStr(n1):
            if n1 == 1:
                return '0'
            else:
                prev = findNthStr(n1 - 1)
                return prev + '1' + reverse(invert(prev))
                
        return findNthStr(n)[k-1]

class Solution:
    def invert(self, t):
        ret = ''
        for i in t:
            if i == '0':
                ret += '1'
            else:
                ret += '0'
        return ret
    
    def findKthBit(self, n: int, k: int) -> str:
        i = 1
        l = list()
        l.append('0')
        while i <= n:
            t = l[-1]
            ans = t + '1' 
            ans += self.invert(t[::-1])
            l.append(ans)
            i += 1
        return l[-1][k - 1]
            
            


class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        dp = ['0'] * n
        for i in range(1, n):
            dp[i] = dp[i-1] + '1' + ''.join([str(1-int(n)) for n in dp[i-1]])[::-1]
        return dp[-1][k-1]

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        s = '0'
        inv = '1'
        rev_inv = '1'
        
        for i in range(n-1):
            s = s + '1' + rev_inv
            inv = ''
            rev_inv = ''
            for j in range(len(s)):
                if s[j]=='0':
                    inv+='1'
                else:
                    inv+='0'
            rev_inv = inv[::-1]
            
        return s[k-1]

class Solution:
    
        
    
    def findKthBit(self, n: int, k: int) -> str:
        s=[]
        for i in range(n):
            if i==0:
                s.append(['0'])
            else:
                temp=(s[i-1]).copy()
                for j in range(len(temp)):
                    if temp[j]=='0':
                        temp[j]='1'
                        
                        # temp2=''
                        # temp=(temp2.join(temp)) 
                        
                        
                    else:
                        # temp=list(temp)
                        temp[j]='0'
                        
                        # temp2=''
                        # temp=(temp2.join(temp)) 
                temp=temp[::-1]
                
                s.append([])
                for zz in s[i-1]:
                    s[i].append(zz)
                s[i].append('1')
                for zz in temp:
                    s[i].append(zz)
                
                
        
        # for i in (s[k-1]):
        #     print(i)
        return (s[-1][k-1])
                


class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        def helper(memo):
            ans = ''
            for c in memo:
                if c == '0':
                    ans += '1'
                else:
                    ans += '0'
            return ans
        memo = '0'
        for i in range(1, n + 1):
            memo = memo + '1' + helper(memo)[::-1]
        return memo[k - 1]

vals = [0]
for _ in range(20):
    vals += [1] + [1-x for x in reversed(vals)]
    

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        return str(vals[k-1])

bins = [[0]]
for _ in range(20):
    bins.append(bins[-1] + [1] + [1-x for x in reversed(bins[-1])])
    

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        return str(bins[n-1][k-1])

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        if n==1:
            return '0'
        if n==2:
            return ['0','1','1'][k-1]
        record=[0,1,1]
        for i in range(n-2):
            record=record+[1]+record
            l=len(record)
            record[l//2+l//2//2+1]=0
    
        return str(record[k-1])

class Solution:  
    def invert(s):
        inv_s = ''
        for char in s:
            if char == '1':
                inv_s += '0'
            else:
                inv_s += '1'

        return inv_s
    
    answer = ['0']
    
    for i in range(1, 21):
        prev_s = answer[i-1]
        answer.append(prev_s + '1' + invert(prev_s)[::-1])
        
    
    def findKthBit(self, n: int, k: int) -> str:
        
#         def invert(s):
#             inv_s = ''
#             for char in s:
#                 if char == '1':
#                     inv_s += '0'
#                 else:
#                     inv_s += '1'

#             return inv_s
        
#         result = ['0']
        
#         for i in range(1, 21):
#             prev_s = result[i-1]
#             # print(self.invert(prev_s))
#             result.append(prev_s + '1' + invert(prev_s)[::-1])
#             # break
            
        return self.answer[n-1][k-1]


class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        s = '0'
        for i in range(2,n + 1):
            sRevInv = ''.join(['1' if c == '0' else '0' for c in s[::-1]])
            s = s + '1' + sRevInv
            if len(s) >= k:
                return s[k-1]
        return s[k-1]

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        s = '0'
        for i in range(2,n + 1):
            sRevInv = ''.join(['1' if c == '0' else '0' for c in s[::-1]])
            s = s + '1' + sRevInv
            if len(s) >= k:
                break
        return s[k-1]

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        s = '0'
        for i in range(2,n + 1):
            s = s + '1' + ''.join(['1' if c == '0' else '0' for c in s[::-1]])
            if len(s) >= k:
                break
        return s[k - 1]

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        def invert(x):
            return [0 if i == 1 else 1 for i in x]
        
        S = [0]
        i = 1
        
        while i < n and len(S) < k:
            S.append(1)
            S.extend((invert(S[:-1])[::-1]))
            i += 1
            
        return str(S[k - 1])

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        def operator(s):
            t = reversed([('0' if i == '1' else '1') for i in s])
            return s + '1' + ''.join(t)
        s = '0'
        while len(s) < k:
            s = operator(s)
        return s[k - 1]

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        switch = {'0': '1', '1': '0'}
        s = '0'
        while len(s) < k:
            s = s + '1' + ''.join(switch[i] for i in reversed(s))
        return s[k-1]

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        l = [0]
        for _ in range(n-1):
            l = l + [1] + [1-b for b in reversed(l)]
            if len(l) >= k:
                return str(l[k-1])
        return str(l[k-1])

class Solution:
    s = [0]

    def findKthBit(self, n: int, k: int) -> str:
        while len(self.s) < k:
            self.s = self.s + [1] + [n ^ 1 for n in self.s[::-1]]

        return str(self.s[k - 1])

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        def inner(n,k):
            if n==1:
                re=0
            elif k==(2**(n-1)):
                re=1
            elif k<(2**(n-1)):
                re=inner(n-1,k)
            else:
                re=inner(n-1,2**n-k)^1
            return re
        return str(inner(n,k))


class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        def invert(l):
            result = []
            for item in l:
                if item == '0':
                    result.append('1')
                else:
                    result.append('0')
            return result
                    
        string = '0'
        while len(string)<k:
            string = string + '1'
            addition = invert(string[0:len(string)-1])
            addition.reverse()
            addition = ''.join(addition)
            string = string + addition
        
        return string[k-1]


class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        #Si = Si-1 + \"1\" + reverse(invert(Si-1)) for i > 1
        s=''
        def recurse(n):
            nonlocal s
            if n<=1:
                return '0'
            else:
                _str=recurse(n-1)
                s=_str+'1'+self.reverse(self.invert(_str))
                return s
        return recurse(n)[k-1]
        
    def invert(self,string):
        return ''.join(['0' if char=='1' else '1' for char in string])
    
    def reverse(self,string):
        return string[::-1]


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

        cur = '0'
        
        while len(cur) < k:
            cur = cur + '1' + ''.join('1' if b == '0' else '0' for b in reversed(cur))
            
        return cur[k-1]

# 1545. Find Kth Bit in Nth Binary String: https://leetcode.com/problems/find-kth-bit-in-nth-binary-string/
# Author: Ragy Morkos

#######################################################################

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        s = [0]
        for _ in range(2, n+1):
            s = s + [1] + [1 - x for x in s][::-1]
        return str(s[k-1])

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        memo = {}
        def dp(s):
            if s in memo:
                return memo[s]
            if s == 1:
                return '0'
            temp = dp(s-1)
            res = temp + '1' + ''.join(['0' if b == '1' else '1' for b in temp])[::-1]
            memo[s] = res
            return res
        
        return dp(n)[k-1]

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        curr = '0'
        for x in range(2, n + 1):
            nxt = curr + '1' + self.invert(curr)[::-1]
            curr = nxt
        return curr[k - 1]
            
        
    def invert(self, s):
        return ''.join(['1' if x == '0' else '0' for x in s])

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        def invert(data):
            ans = ''
            for val in data:
                ans += '1' if val == '0' else '0'
            return ans

        output = '0'
        for i in range(1, n+1):
            output += '1' + invert(output)[::-1]
            if len(output) >= k:
                break   
        return output[k - 1]


class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        
        s2 = '011'
        if k<=3:
            return s2[k-1]
        
        if k==2**(n-1):
            return '1'
        elif k<2**(n-1):
            return self.findKthBit(n-1,k)
        else:
            ans = self.findKthBit(n-1, 2**(n) - k)
            return '1' if ans=='0' else '0'


class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        def helper(res,k):
            if k==0:
                return res
            invert = ['1' if i=='0' else '0' for i in res]
            invert = ''.join(invert)
            res = res + '1' + invert[::-1]
            return helper(res,k-1)
        res = helper('0',n-1)
        return res[k-1]

class Solution:
    
    def findKthBit(self, n: int, k: int) -> str:
        
        A = [0]
        
        while k > len(A):
            A.append(1)
            for i in range(len(A)-2,-1,-1):
                A.append(A[i] ^ 1)
                
        return str(A[k-1])

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        def revinv(x):
          ans = []
          for c in x:
            if c=='0':
              ans.append('1')
            else:
              ans.append('0')
          return ''.join(reversed(ans))
        s = '0'
        while k>len(s):
          s = s + '1' + revinv(s)
        return s[k-1]

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        m = 2 ** n - 1
        if k == 1 or 0 < m - k < 4:
            return '0'
        if k == m or k < 5:
            return '1'
        s = [0]
        for _ in range(n-1):
            s += [1] + [x ^ 1 for x in reversed(s)]
        return str(s[k-1])

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        dp = [0]
        while len(dp) < k:
            dp.append(1)
            for i in range(len(dp)-2, -1 , -1):
                dp.append(dp[i]^1)
        
        return str(dp[k-1])

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        m = 2 ** n - 1
        if k == 1:
            return '0'
        if k < 5:
            return '1'
        s = [0]
        for _ in range(n-1):
            s += [1] + [x ^ 1 for x in reversed(s)]
        return str(s[k-1])

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        a = [0]
        while k > len(a):
            a.append(1)
            for i in range(len(a) - 2, -1, -1):
                a.append(a[i] ^ 1)
        return str(a[k - 1])

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        s = [0]
        for _ in range(n-1):
            s += [1] + [x ^ 1 for x in reversed(s)]
        return str(s[k-1])

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        s = '0'
        if n == 1:
            return '0'
        for i in range(1, n):
            s_i = s[::-1]
            s = s+'1'+''.join(['1' if c == '0' else '0' for c in s_i])
        # print(s)
        return s[k-1]

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

        def build_string(n):
            previous = '0'

            for i in range(1, n):
                invert = ''
                for c in previous:
                    if c == '1':
                        invert += '0'
                    else:
                        invert += '1'
                previous = previous + '1' + invert[::-1]
            return previous

        ans = build_string(n)
        return ans[k-1]

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        s = '011'
        if k < 4:
            return s[k - 1]
            
        d = {'0':'1', '1':'0'}
        for i in range(n):
            s += '1'
            if len(s) == k:
                return '1'
            else:
                for x in s[:-1][::-1]:
                    s += d[x]
                    if len(s) == k:
                        return d[x]