class Solution:
def findKthBit(self, n: int, k: int) -> str:
rdit = {}
idit = {}
res = self.dfs(n)
return res[k-1]
def dfs(self, idx):
if idx == 1:
return "0"
return self.dfs(idx - 1) + "1" + self.invert(self.dfs(idx - 1))[::-1]
def invert(self,s):
# print(s,"s")
s = s.replace("1","2")
s = s.replace("0","1")
s = s.replace("2","0")
# print(s,"S")
return s