1545. Find Kth Bit in Nth Binary String

Time: O(n)

Space: O(n)

Intuition

Binary string generated by flipping 0→"01" and 1→"10" repeatedly. Find k-th character efficiently using recursion without generating the string.

Algorithm

1After n generations, length = 2^n. Find k-th in step n:
2If k <= 2^(n-1): same as k-th in step n-1.
3Else: k-th in step n = NOT of (k-2^(n-1))-th in step n-1.

Common Pitfalls

•Parent-child relationship: child at position k is the complement of parent at position k - half_length. Use recursion/binary lifting.

1545.cs

// Approach: Recursive divide — mid is '1', left half recurse normally, right half recurse mirrored with flipped result.
// Time: O(n) Space: O(n)

public class Solution
{
    public char FindKthBit(int n, int k)
    {
        if (n == 1)
            return '0';
        int midIndex = (int)Math.Pow(2, n - 1); // 1-indexed
        if (k == midIndex)
            return '1';
        if (k < midIndex)
            return FindKthBit(n - 1, k);
        return FindKthBit(n - 1, midIndex * 2 - k) == '0' ? '1' : '0';
    }
}

Was this solution helpful?