Om Shree

Posted on Mar 3

🧬 Beginner-Friendly Guide 'Find Kth Bit in Nth Binary String' - Problem 1545 (C++, Python, JavaScript)

#programming #cpp #javascript #python

Generating massive binary strings can quickly exhaust your computer's memory. This problem challenges you to find a specific character within a complex, growing sequence without actually building the entire string. By leveraging the symmetrical properties of the sequence, we can use a "divide and conquer" strategy to pinpoint our answer.

Problem Summary

You're given:

An integer $n$, representing the $n^{th}$ generation of a binary string $S_n$.
An integer $k$, representing the 1-indexed position of the bit you need to find.

Your goal:
Return the value of the $k^{th}$ bit in $S_n$ as a character ('0' or '1').

Intuition

The structure of $S_n$ follows a very specific pattern: $S_n = S_{n-1} + "1" + \text{reverse}(\text{invert}(S_{n-1}))$.

If we look closely at the length of these strings, $S_n$ has a length of $2^n - 1$. This means there is always a "middle" bit at position $2^{n-1}$. This middle bit is always '1' (except for the base case $S_1 = "0"$).

Because the second half of the string is just a transformed version of the first half, we don't need to generate it. We can use recursion to "look back" at previous versions of the string:

Base Case: If $n = 1$, the bit is always '0'.
Middle Case: If $k$ is exactly at the middle position, the bit is '1'.
Left Side: If $k$ is less than the middle, the bit is the same as the $k^{th}$ bit in $S_{n-1}$.
Right Side: If $k$ is greater than the middle, the bit is the inverted version of a bit in $S_{n-1}$. Because the right side is reversed, the $k^{th}$ bit in $S_n$ corresponds to the bit at position $(\text{Total Length} + 1 - k)$ in $S_{n-1}$.

Walkthrough: Understanding the Examples

Example: $n = 3, k = 1$

$S_3$ length is 7. Middle is 4.
$k=1$ is less than the middle (4).
We look for the $1^{st}$ bit in $S_2$.
$S_2$ length is 3. Middle is 2.
$k=1$ is less than the middle (2).
We look for the $1^{st}$ bit in $S_1$.
Base Case: $n=1$ returns '0'.

Example: $n = 4, k = 11$

$S_4$ length is 15. Middle is 8.
$k=11$ is greater than 8.
The corresponding position in $S_3$ is $16 - 11 = 5$.
We find the $5^{th}$ bit of $S_3$ and invert it.
In $S_3$, middle is 4. $k=5$ is greater than 4.
Corresponding position in $S_2$ is $8 - 5 = 3$.
We find the $3^{rd}$ bit of $S_2$ and invert the result again.
In $S_2$, middle is 2. $k=3$ is greater than 2.
Corresponding position in $S_1$ is $4 - 3 = 1$.
$S_1$ at $k=1$ is '0'.
Following the chain of inversions: '0' $\rightarrow$ '1' $\rightarrow$ '0' $\rightarrow$ '1'. Final result is '1'.

Code Blocks

C++

class Solution {
 public:
  char findKthBit(int n, int k) {
    if (n == 1)
      return '0';

    // The middle index is 2^(n-1)
    int midIndex = 1 << (n - 1);

    if (k == midIndex)
      return '1';
    if (k < midIndex)
      return findKthBit(n - 1, k);

    // If k is in the right half, find the bit in the reflected position
    // and invert it (0 becomes 1, 1 becomes 0)
    return findKthBit(n - 1, midIndex * 2 - k) == '0' ? '1' : '0';
  }
};

Python

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        if n == 1:
            return "0"

        # Calculate middle index using bit shift for 2^(n-1)
        mid_index = 1 << (n - 1)

        if k == mid_index:
            return "1"
        elif k < mid_index:
            return self.findKthBit(n - 1, k)
        else:
            # Mirror the position and invert the result
            res = self.findKthBit(n - 1, mid_index * 2 - k)
            return "1" if res == "0" else "0"

JavaScript

/**
 * @param {number} n
 * @param {number} k
 * @return {character}
 */
var findKthBit = function(n, k) {
    if (n === 1) {
        return '0';
    }

    const midIndex = Math.pow(2, n - 1);

    if (k === midIndex) {
        return '1';
    } else if (k < midIndex) {
        return findKthBit(n - 1, k);
    } else {
        // Mirror position: (Total Length + 1) - k
        // Total Length is (midIndex * 2) - 1
        const reflectedBit = findKthBit(n - 1, midIndex * 2 - k);
        return reflectedBit === '0' ? '1' : '0';
    }
};

Key Takeaways

Recursive Symmetry: Many string generation problems can be solved by recognizing how the current state relates to the previous state without building the full data structure.
Divide and Conquer: By halving the search space at each step, we achieve a time complexity of $O(n)$, which is much better than the $O(2^n)$ required to build the string.
Bit Manipulation: Using 1 << (n - 1) is a fast and efficient way to calculate powers of 2 in many programming languages.

Final Thoughts

This problem is a classic example of why understanding recursion is vital for technical interviews. In a real-world system, such as a file compression utility or a data recovery algorithm, you might need to extract specific pieces of data from a pattern-based stream. Generating the entire stream would crash your system if the "n" was large, but using these mathematical properties allows your code to stay lightweight and fast.

DEV Community