Find Kth Bit in Nth Binary String - Video Solutions

Problem Overview: The binary string S_n is built recursively. S_1 = "0". For every next step: S_n = S_{n-1} + "1" + reverse(invert(S_{n-1})). The task is to return the kth bit (1-indexed) in S_n without necessarily constructing the entire string.

Approach 1: Iterative Construction (O(2^n) time, O(2^n) space)

This method directly simulates the definition of the sequence. Start from S_1 = "0". For each step, generate the next string by appending "1" and then the reversed inverted version of the current string. Inversion flips every bit (0 → 1, 1 → 0) and reversing changes the order. Once the string for n is built, return the character at index k - 1. The approach uses basic string operations and straightforward simulation. The downside is exponential growth: the string length becomes 2^n - 1, which quickly becomes impractical for larger n.

Approach 2: Recursive Mathematical Insight (O(n) time, O(n) space)

The recursive structure of the string reveals a pattern that avoids building it. The total length of S_n is 2^n - 1, and the middle element is always '1'. If k equals the middle index, the answer is immediately '1'. If k is in the left half, the problem reduces to finding the kth bit of S_{n-1}. If k lies in the right half, map it to the mirrored position in the left half using k' = length - k + 1, then invert the result. This works because the right half is exactly reverse(invert(S_{n-1})). The recursion depth is at most n, so the time complexity becomes O(n) with O(n) stack space. This technique leverages properties of recursion and symmetry in the string construction.

Recommended for interviews: Interviewers typically expect the recursive mathematical approach. The brute-force construction shows you understand how the sequence is generated, but recognizing the symmetry and middle pivot demonstrates stronger problem-solving skills. The optimal approach reduces exponential work to a simple recursive reduction based on position.