Find Kth Bit in Nth Binary String

Problem Description

Given two positive integers n and k, the binary string S_n is formed as follows:

• S_1 = "0"
• S_i = S_{i - 1} + "1" + reverse(invert(S_{i - 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). Return the k-th bit in S_n. It is guaranteed that k is valid for the given n.

Key Insights

• The string S_n grows exponentially in length; specifically, the length of S_n is 2^n - 1.
• The concatenation pattern allows us to determine the value of the k-th bit without generating the entire string, leveraging the recursive structure.
• If k is in the first half of S_n, it belongs to S_{n-1}. If k is at the middle, it's '1'. If k is in the second half, we can compute its position in the inverted section.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To find the k-th bit in the n-th binary string S_n, we can use a recursive approach:

1. If k is in the first half of the string, we can look at S_{n-1} directly.
2. If k is exactly the middle index, the bit is '1'.
3. If k is in the second half, we need to find its corresponding position in S_{n-1}, invert it, and reverse it.

This avoids the need to construct the entire string, thus saving both time and space.

Code Solutions