Generated by Codex with GPT 5.6 Sol High

Quick facts

The problem in plain language

The problem defines a family of binary strings without asking us to construct them directly. It begins with S1 = "0". Each later string consists of three parts: the previous string, a middle 1, and a reversed copy of the previous string with every bit flipped.

For example, S3 is 0111001. Given n and a one-based position k, the task is to return the bit at that position in Sn.

The tempting solution is to generate every string through Sn and index into the result. That works for the stated limit of n <= 20, but it misses the useful structure: the string has exponential length even though one requested bit can be found in only n steps.

Deriving the optimal solution

The length of Sn is 2^n - 1, so its middle position is 2^(n - 1). That divides any query into three cases:

  1. If k is the middle position, the answer is the inserted 1.
  2. If k is left of the middle, it refers to the same position in S(n - 1).
  3. If k is right of the middle, it belongs to reverse(invert(S(n - 1))).

The third case is the only subtle one. Reflecting a position from the right half back into S(n - 1) changes k to 2^n - k. Because the right half is also inverted, the eventual answer must be flipped.

After reflecting, the problem is one level smaller. Repeating this process eventually reaches either a middle bit or S1. A Boolean flag can remember whether the path crossed an odd number of inverted right halves. This removes the need for recursion as well as the need to build any strings.

For n = 4 and k = 11, the middle is position 8. Position 11 is in the right half, so it reflects to position 16 - 11 = 5 in S3, and the inversion flag turns on. Position 5 is in the right half of S3, so it reflects to position 8 - 5 = 3 in S2, and the flag turns off. Position 3 is in the right half of S2; it reflects to the only bit in S1, and the flag turns on again. The base bit is 0, so one net inversion produces 1.

This algorithm takes O(n) time and O(1) extra space. Constructing the string would take O(2^n) time and space.

Python solution

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        """Return the one-based k-th bit of the recursively defined string Sn."""
        if n < 1:
            raise ValueError("n must be positive")

        string_length = (1 << n) - 1
        if not 1 <= k <= string_length:
            raise ValueError("k must identify a position in Sn")

        is_inverted = False

        while n > 1:
            middle_position = 1 << (n - 1)

            if k == middle_position:
                # Every level inserts a 1 at its center. Apply any inversion
                # accumulated while reflecting through outer right halves.
                return "0" if is_inverted else "1"

            if k > middle_position:
                # Mirror the right-half position into S(n - 1). The right
                # half is inverted, so toggle the pending inversion as well.
                k = (1 << n) - k
                is_inverted = not is_inverted

            # A left-half position is already the same index in S(n - 1).
            n -= 1

        # S1 contains only 0; apply the parity of all pending inversions.
        return "1" if is_inverted else "0"

Why the algorithm is correct

At every level, the algorithm preserves an equivalent query in the previous string. A left-half position is copied directly from S(n - 1), so neither its index nor its bit changes. A right-half position is the reflected position in S(n - 1) with its bit inverted, so reflecting the index and toggling is_inverted preserves the answer. A middle position is the inserted 1, adjusted by exactly the inversions accumulated at higher levels.

Each iteration reduces n by one. When the loop reaches S1, the underlying bit is known to be 0; applying the recorded inversion parity gives the requested bit in the original string. These cases cover every valid position, so the algorithm always returns the correct result.

Interview follow-ups

Could you solve it recursively instead?

Yes. The recursive function uses the same three cases: return 1 at the middle, recurse unchanged for the left half, and recurse on the mirrored position and flip the result for the right half. This is often the most direct expression of the definition and is easy to prove by induction. It still takes O(n) time, but its call stack uses O(n) space, while the iterative version uses O(1) extra space.

What if the interviewer asks you to construct the complete string?

Build from S1 upward. At each level, append 1, then append the reversed and inverted previous string. The work is proportional to the final output size, so both time and space are O(2^n). That is optimal when the complete string itself is required, but wasteful when only one bit is requested.

How would you answer many queries for the same n?

There is a tradeoff between preprocessing and per-query cost. The structure-aware algorithm answers each query in O(n) time with constant extra space, so q queries cost O(qn). Alternatively, constructing Sn once costs O(2^n) time and space, after which each query is O(1). Precomputation becomes attractive only when there are enough queries to justify storing the exponential-size string.

Can the inversion flag be replaced with arithmetic?

Yes. Instead of a Boolean, keep an inversion count modulo two and XOR it with each right-half transition. At the end, XOR that parity with the base bit. The meaning and complexity are unchanged; the Boolean form is usually clearer in an interview because it states the invariant directly: the final bit is flipped exactly when the number of inverted right-half transitions is odd.

What changes if k is zero-based?

The overall idea remains the same, but the midpoint and reflection formulas must be adjusted consistently. For a zero-based string of length 2^n - 1, the middle index is 2^(n - 1) - 1, and a right-half index reflects to length - 1 - k. Converting the input to one-based indexing at the boundary is often safer than maintaining two subtly different formulas throughout the solution.

What edge cases should be tested?

The base case n = 1, k = 1 checks the final return path. Querying the middle at several levels checks the immediate 1 case. The first and last positions exercise repeated left and right transitions, and values immediately beside the middle catch reflection off-by-one errors. It is also useful to compare the optimized method with explicitly generated strings for every position at small values of n.