Find Kth Bit in Nth Binary String

Find Kth Bit in Nth Binary String

What is this problem about?

The Find Kth Bit in Nth Binary String interview question describes a sequence of strings $S_n$ generated by a rule:

• $S_1 = "0"$
• $S_n = S_{n-1} + "1" + reverse(invert(S_{n-1}))$ You need to return the $k$-th character of $S_n$ (1-indexed).

Why is this asked in interviews?

Companies like Microsoft and Bloomberg use this to test Recursion and mathematical observation skills. Since the length of $S_n$ doubles at each step ($2^n - 1$), you cannot construct the string for large $n$. It evaluations whether you can use the recursive definition to "mirror" the search back into $S_{n-1}$.

Algorithmic pattern used

This problem uses Recursion with Mirroring.

1. The middle bit of $S_n$ is always "1" at index $2^{n-1}$.
2. If $k$ is the middle bit, return '1'.
3. If $k$ is in the first half, it’s the same as the $k$-th bit of $S_{n-1}$.
4. If $k$ is in the second half, it corresponds to a bit in $S_{n-1}$ that has been reversed and inverted. Its original position was $Length - k + 1$.

Example explanation

$S_1 = "0"$. Find $S_3, k=1$.

1. $S_2 = "0" + "1" + "1" = "011"$.
2. $S_3 = "011" + "1" + "001" = "0111001"$.
3. $k=1$: It's in the first half of $S_3$, so it's the 1st bit of $S_2$.
4. The 1st bit of $S_2$ is the 1st bit of $S_1$, which is "0". Result: '0'.

Common mistakes candidates make

• String Construction: Attempting to build the string, which leads to $O(2^n)$ space and potential Memory Limit Exceeded.
• 1-based indexing: Errors when calculating the mirrored index in the second half.
• Inversion logic: Forgetting to flip '0' to '1' and '1' to '0' when mapping to the second half.

Interview preparation tip

Always look at the "structure" of the recursive step. If it involves a reverse or invert, the search can usually be simplified by mapping the target index back to a previous state. This is a common Recursive logic interview pattern.