Find kth bit in nth Binary String

XXX. Find Kth Bit in Nth Binary String

Recursion

String Manipulation

Problem Statement:

Given two integers n and k, find the kth bit in the binary string generated according to the following rules:

1. Start with S1 = "0".
2. For each subsequent string Si, construct it as Si-1 + "1" + reverse(invert(Si-1)).

Return the kth bit of Sn as a character.

Algorithm:

The problem can be solved recursively by observing the structure of the binary strings:

1. Base case: For n = 1, the string is "0". Return "0" for any value of k.
2. Compute the length of the string Sn, which is 2n - 1.
3. Divide the string into three parts:
   • The first half corresponds to Sn-1.
   • The middle character is "1".
   • The second half is the reverse of the inverted Sn-1.
4. Determine the position of k:
   • If k is in the first half, recurse on Sn-1.
   • If k is the middle character, return "1".
   • If k is in the second half, map it to the first half, recurse, and invert the result.

Complexity:

Time Complexity: O(n), as the recursion depth depends on n.
Space Complexity: O(n), due to the recursion stack.

Java Implementation:

public class Solution {

    public char findKthBit(int n, int k) {
        // Base case: for S1, return '0'
        if (n == 1) return '0';

        // Calculate the length of Sn
        int len = (1 << n) - 1; // Equivalent to 2^n - 1

        // If k is in the first half of the string, recurse with n-1
        if (k < len / 2 + 1) 
            return findKthBit(n - 1, k);

        // If k is exactly in the middle, return '1'
        else if (k == len / 2 + 1) 
            return '1';

        // If k is in the second half of the string
        else {
            // Find the corresponding bit in the first half and invert it
            char correspondingBit = findKthBit(n - 1, len - k + 1);
            return (correspondingBit == '0') ? '1' : '0';
        }
    }
}