Find Kth Bit in Nth Binary String

medium string recursion divide and conquer

Problem

Build a sequence of binary strings where S₁ = "0" and, for i > 1, S_i = S_i-1 + "1" + reverse(invert(S_i-1)). Here invert flips every bit (0↔1) and reverse reverses the string. Given n and a 1-based index k, return the k^th character of S_n as "0" or "1", without materializing the whole string.

Inputn = 4, k = 11

Output"1"

S₄ = "0111001101 1 0001"; the 11th character is "1".

Inputn = 3, k = 1

Output"0"

S₃ = " 0 111001"; the 1st character is "0".

n (1 to 20)

k (1 to 2^n − 1)

def find_kth_bit(n, k):
    length = (1 << n) - 1   # length of S_n
    invert = 0
    while length > 1:
        mid = (length + 1) // 2
        if k == mid:
            return "0" if invert else "1"   # middle bit is "1"
        if k > mid:
            k = length - k + 1   # mirror into left half
            invert ^= 1          # right half is reverse(invert(left))
        length = (length - 1) // 2   # shrink to S_(i-1)
    return "1" if invert else "0"    # base bit S_1 is "0"

function findKthBit(n, k) {
  let length = (1 << n) - 1;   // length of S_n
  let invert = 0;
  while (length > 1) {
    const mid = (length + 1) / 2;
    if (k === mid) {
      return invert ? "0" : "1";   // middle bit is "1"
    }
    if (k > mid) {
      k = length - k + 1;   // mirror into left half
      invert ^= 1;          // right half is reverse(invert(left))
    }
    length = (length - 1) / 2;   // shrink to S_(i-1)
  }
  return invert ? "1" : "0";   // base bit S_1 is "0"
}

char findKthBit(int n, int k) {
    int length = (1 << n) - 1;   // length of S_n
    int invert = 0;
    while (length > 1) {
        int mid = (length + 1) / 2;
        if (k == mid) {
            return invert == 1 ? '0' : '1';   // middle bit is '1'
        }
        if (k > mid) {
            k = length - k + 1;   // mirror into left half
            invert ^= 1;          // right half is reverse(invert(left))
        }
        length = (length - 1) / 2;   // shrink to S_(i-1)
    }
    return invert == 1 ? '1' : '0';   // base bit S_1 is '0'
}

char findKthBit(int n, int k) {
    int length = (1 << n) - 1;   // length of S_n
    int invert = 0;
    while (length > 1) {
        int mid = (length + 1) / 2;
        if (k == mid) {
            return invert ? '0' : '1';   // middle bit is '1'
        }
        if (k > mid) {
            k = length - k + 1;   // mirror into left half
            invert ^= 1;          // right half is reverse(invert(left))
        }
        length = (length - 1) / 2;   // shrink to S_(i-1)
    }
    return invert ? '1' : '0';   // base bit S_1 is '0'
}

Explanation

Each S_n is built from S_n-1 with a fixed recipe: S_n-1, then a single "1" in the dead center, then reverse(invert(S_n-1)). So the string has a self-similar structure, and its length is exactly 2ⁿ − 1. We never build it; we just reason about where position k lands.

The center sits at mid = (length + 1) / 2. There are three cases. If k == mid, that character is the inserted "1" — done (flipped if we have accumulated inversions).

If k < mid, position k lies in the left half, which is literally S_n-1. We keep k and shrink to the smaller string.

If k > mid, position k lies in the right half, which is reverse(invert(left)). Mirroring across the center maps it back to the left half at k = length − k + 1, and because of the invert we toggle an invert flag. We then shrink to S_n-1.

We loop until length == 1, i.e. S₁ = "0". The answer is "0" unless an odd number of inversions toggled it to "1". This runs in O(n) steps with O(1) memory — no string is ever allocated.

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