Find Kth Bit in Nth Binary String — Medium Problem & Solution

Problem statement

Binary strings S1, S2, … are built as follows:

• S1 = "0";
• Si = S(i−1) + "1" + reverse(invert(S(i−1))) for i > 1, where invert turns every 0 into 1 and every 1 into 0.

So S2 = "011", S3 = "0111001" and S4 = "011100110110001".

Given n and k, return the k-th bit (1-indexed) of Sn as a one-character string, "0" or "1".

Example 1

Input: n = 3, k = 5
Output: 0
Explanation: S3 = 0111001; its fifth bit is 0.

Example 2

Input: n = 4, k = 10
Output: 1

Example 3

Input: n = 1, k = 1
Output: 0

Constraints

• 1 <= n <= 20
• 1 <= k <= 2^n - 1

How to solve Find Kth Bit in Nth Binary String

Each Sn is S(n−1), a middle 1, and a mirrored inverted copy of S(n−1), so the k-th bit can be traced back to a position in a shorter string without building anything.

Approach

1. Keep a flag flipped = false.
2. While n > 1: let mid = 2^(n−1). If k == mid, the bit is 1 (inverted if flipped). If k > mid, replace k by 2^n − k and toggle flipped. Then decrease n.
3. When n reaches 1 the bit is 0 (inverted if flipped).

Why it works

The right part of Sn holds S(n−1) reversed, so position mid + j corresponds to position mid − j = 2^n − k of S(n−1), with its value inverted; the left part needs no change. Every step halves the string, so after at most n − 1 steps the position is either a middle bit or the single bit of S1, and the number of inversions picked up along the way decides the final value.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Building S20 costs about a million characters per query — fine once, wasteful per call.
• The mirror index is 2^n − k, not 2^n − k − 1 or k − mid.
• The answer is a string ("0"/"1"), not a number.

Reference solution

Python

def findKthBit(n: int, k: int) -> str:
    flipped = False
    while n > 1:
        mid = 1 << (n - 1)
        if k == mid:
            return "0" if flipped else "1"
        if k > mid:
            k = (1 << n) - k
            flipped = not flipped
        n -= 1
    return "1" if flipped else "0"

JavaScript

var findKthBit = function(n, k) {
    var flipped = false;
    while (n > 1) {
        var mid = 1 << (n - 1);
        if (k === mid) return flipped ? "0" : "1";
        if (k > mid) {
            k = (1 << n) - k;
            flipped = !flipped;
        }
        n--;
    }
    return flipped ? "1" : "0";
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Ambiguous Coordinates Medium
• Generate Binary Strings Without Adjacent Zeros Medium
• Splitting a String Into Descending Consecutive Values Medium
• Letter Case Permutation Medium
• Lexicographically Smallest Equivalent String Medium
• Extra Characters in a String Medium