Problem

Given two positive integers n and k, the binary string Sn is formed according to the following rules:

• S1 = "0"
• When i > 1: Si = Si-1 + "1" + reverse(invert(Si-1))

where + denotes concatenation, reverse(x) returns the string x reversed, and invert(x) flips every bit in x (0 becomes 1 and 1 becomes 0).

The first 4 strings in this sequence are:

• S1 = "0"
• S2 = "011"
• S3 = "0111001"
• S4 = "011100110110001"

Return the k-th bit in Sn. It is guaranteed that k is within the valid range for Sn.

Solution

My first attempt was a brute-force approach — directly generating Sn. However, when n is large, Sn becomes extremely long, causing memory overflow.

/**
 * @param {number} n
 * @param {number} k
 * @return {character}
 */
var findKthBit = function (n, k) {
  var reverseR = function (input) {
    return input
      .split("") // 拆分成数组 ["0", "1", "1", "1", "0"]
      .map((char) => char ^ 1) // 翻转每一位: [1, 0, 0, 0, 1]
      .reverse() // 反转数组顺序: [1, 0, 0, 0, 1]
      .join(""); // 拼回字符串 "10001"
  };
  let S = "0";
  for (let i = 1; i < n; i++) {
    S = S + "1" + reverseR(S);
  }
  return S[k - 1];
};

I then tried a mathematical bit-flip approach. Observing $S_i = S_{i-1} + "1" + \text{reverse}(\text{invert}(S_{i-1}))$:

Length pattern: $|S_n| = 2^n - 1$.

• For example, $S_1$ has length $2^1-1=1$, and its middle bit is position $1$.
• $S_2$ has length $2^2-1=3$, and its middle bit is position $2$.
• $S_3$ has length $2^3-1=7$, and its middle bit is position $4$.

Three cases for the position of k:

• Left half (k < mid): This is an exact copy of $S_{n-1}$, so we simply ask "what is the $k$-th bit of $S_{n-1}$?"
• Middle ($k = mid$): By the construction rule, this bit is always "1".
• Right half (k > mid): This is the most elegant part. The right half is the reverse-invert of $S_{n-1}$.

Because of the reverse, the 1st character of the right half corresponds to the last character of the left half, and so on.

The mapping formula is: $S_n[k] = \text{invert}(S_{n-1}[2^n - k])$.

For example, to find the 6th bit in $S_3$ (length 7), it corresponds to the result of inverting the $2^3 - 6 = 2$nd bit of $S_2$.

var findKthBit = function (n, k) {
  let flip = false; // 记录需要取反的次数
  while (n > 1) {
    let mid = 1 << (n - 1); // 2^(n-1)
    if (k === mid) {
      // 中间位固定为 1
      let res = 1;
      return (flip ? res ^ 1 : res).toString();
    } else if (k > mid) {
      // 如果在右侧，镜像到左侧，并增加一次取反
      k = 2 * mid - k;
      flip = !flip;
    }
    // 如果在左侧，直接继续看 n-1
    n--;
  }
  // 最终回到 S1，S1 是 "0"
  let res = 0;
  return (flip ? res ^ 1 : res).toString();
};

Why Is mid Equal to $2^{n-1}$?

We can derive the center point (mid) by computing the total length of $S_n$.

Computing the length of $S_n$: Let $L_n$ denote the length of the $n$-th string $S_n$. From the problem rules:

• $S_1 = "0"$, so $L_1 = 1$
• $S_n = S_{n-1} + "1" + \text{modified } S_{n-1}$

The length recurrence is: $L_n = L_{n-1} (\text{left half}) + 1 (\text{middle}) + L_{n-1} (\text{right half})$ i.e., $L_n = 2 \times L_{n-1} + 1$

Listing out the values:

• $L_1 = 1$
• $L_2 = 2 \times 1 + 1 = 3$
• $L_3 = 2 \times 3 + 1 = 7$
• $L_4 = 2 \times 7 + 1 = 15$

Pattern: $L_n = 2^n - 1$

2. Why Do We Search This Way?

Think of it like finding a specific point on an infinitely folded paper strip:

• Old approach (simulation): Fold a blank sheet of paper 20 times to create an enormously long strip, then count from the beginning to the $k$-th point.
• New approach (backtracking/iteration): Look at the already "folded" paper ($S_n$) and ask: is this point $k$ to the left or right of the fold?
  • If it is to the right of the fold, "unfold" it back to the left (mirror mapping) and record that it was flipped once (flip = !flip).
  • If it is to the left, just look directly at the left half.
  • Now the paper is half the size (n--), and you repeat the process until you land exactly on the fold (k === mid) or the paper shrinks to its smallest possible size (n=1).

3. If We Are in the Right Half and S[k]=0, Does Flipping Over Mean S[k]=1?

Why does "flipping over" give us 1?

According to the problem, the right half of $S_i$ is: $\text{reverse}(\text{invert}(S_{i-1}))$. There are two operations here:

• Invert: $0 \to 1$, $1 \to 0$.
• Reverse: positions are mirrored left-to-right.

So if we see a 0 in the right half and trace it back through these two operations:

• Because of invert: it was a 1 before being flipped.
• Because of reverse: its corresponding position is the symmetric point in the left half.

Involution Hell© 2026 byCommunityunderCC BY-NC-SA 4.0