1545. Find Kth Bit in Nth Binary String

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 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.

• divde and conquer solution

class Solution {
public:
    char findKthBit(int n, int k) {
        if(n == 1) return '0';
        int p = pow(2,n) - 1;
        if(k - 1 == p / 2) return '1';
        if(k - 1 < p / 2) return findKthBit(n - 1, k);
        return findKthBit(n - 1, p - k + 1) == '0' ? '1' : '0';
    }
};

• two pointer solution

class Solution {
public:
    char findKthBit(int n, int k) {
        string st = "0";
        int p = 0;
        while(st.size() < k) {
            if(p == st.size() - 1) st.push_back('1');
            else if(p < 0) p = st.size() - 1;
            else {
                if(st[p--] == '0') st.push_back('1');
                else st.push_back('0');
            }
        }
        return st[k-1];
    }
};