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 &gt; 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:


	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.

&nbsp;
Example 1:

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


Example 2:

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


&nbsp;
Constraints:


	1 &lt;= n &lt;= 20
	1 &lt;= k &lt;= 2n - 1


class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        i, s, hash_map = 1, '0', {'1': '0', '0': '1'}
        for i in range(1, n):
            s = s + '1' + ''.join((hash_map[i] for i in s))[::-1]
        return s[k-1]
class Solution {
   private String invert(String s){
        char [] array=s.toCharArray();
        for(int i=0;i<s.length();i++){
            if(array[i]=='1'){
                array[i]='0';
            }
            else{
                array[i]='1';
            }
        }
        return new String(array);
    }
    private String reverse(String s){
        StringBuilder str=new StringBuilder(s);
        return str.reverse().toString();
    }
    private String func(int i){
        if(i==0){
            return "0";
        }
        return func(i-1)+"1"+reverse(invert(func(i-1)));
    }
    public char findKthBit(int n, int k) {
        String s=func(n-1);
        return s.charAt(k-1);
    }
}
class Solution {
public:
    string Reverse(string s){
        for(int i=0;i<s.length()/2;i++){
            swap(s[i],s[s.length()-1-i]);
        }
        return s;
    }

    string invert(string s){
        for(int i=0;i<s.length();i++){
            if(s[i]=='1') s[i]='0';
            else s[i]='1';
        }
        return s;
    }

    string S(int n) {
        if(n==1){
            return "0";
        }
        return S(n-1) + "1" + Reverse(invert(S(n-1)));
    }

    char findKthBit(int n, int k) {
        if(n==1) return '0';
        string s = S(n-1) + "1" + Reverse(invert(S(n-1)));
        return s[k-1];
    }
};
var findKthBit = function(n, k) {
    return recursivelyGenerate(n-1)[k-1];
}

function recursivelyGenerate(bitLength, memo=new Array(bitLength+1)){
    if(bitLength===0) return "0";
    if(memo[bitLength]) return memo[bitLength];
    const save = recursivelyGenerate(bitLength-1);
    memo[bitLength] = save + '1' + reverseInvert(save);
    return memo[bitLength];
}

function reverseInvert(s){
    return s.split("").map(a=>a==='0'?'1':'0').reverse().join("");
}
Find Kth Bit in Nth Binary String