Find Kth Bit in Nth Binary String

Leetcode Problem:

• Find Kth Bit in Nth Binary String

Summary

• Given two positive integers n and k, the binary string S_n is formed by a recursive process
• The problem asks to find the k-th bit in S_n.

Approach

• The approach used is to build the binary string S_n by concatenating the inverted and reversed previous string, and then find the k-th bit in the resulting string.

Complexity

• O(n log n)

Explanation

• The solution iterates through each bit position in the binary string S_n
• For each position, it checks if the current bit position is less than or equal to the current size of the string
• If so, it returns the bit at the current position
• Otherwise, it appends a new bit to the end of the string, inverts and reverses the previous string, and updates the size of the string
• This process is repeated until the k-th bit is found.

Solution Code:

class Solution {
public:
    char arr[2<<20 + 1] = {0};
    char findKthBit(int n, int k) {
        int size = 1;
        for(int i = 0 ; i < n ; i++){
            int s = size;
            if (k <= s) return arr[k-1] + '0';
            arr[s++] = 1;
            for(int i = size-1; i >= 0; i--){
                arr[s++] = arr[i] ^ 1;
            }
            size = s;
        }
        return arr[k - 1] + '0';
    }
};