⚡Flashcard Drill➔
NeetCode #872LC-1545MediumBit Manipulation
← Back to All Problems

#872 · #1545 · Find Kth Bit in Nth Binary String(找出第 N 个二进制字符串中的第 K 位)

📌 Problem Statement & Constraints

The binary string S_1 is 0, and for n > 1 the string S_n is S_{n-1} followed by 1 followed by the reverse of the bit-inverted S_{n-1}. Given n and k, return the k-th bit (1-indexed) of S_n. Constraints: 1 <= n <= 20, 1 <= k <= 2^n - 1.

💡 Core Algorithmic Approaches

  1. The length of S_n is 2^n - 1, and its middle position 2^(n-1) is always 1.
  2. If k is the middle position, the answer is 1 without any recursion.
  3. If k lies in the left half, it is the k-th bit of S_{n-1}.
  4. If k lies in the right half, it mirrors position length - k + 1 of the left half, with the bit inverted.

💻 Benchmark Python3 Implementation

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        if n == 1:
            return "0"
        length = (1 << n) - 1           # length of S_n
        mid = 1 << (n - 1)              # index of the middle bit
        if k == mid:
            return "1"
        if k < mid:
            return self.findKthBit(n - 1, k)
        # right half: mirror the position and invert the bit
        mirrored = length - k + 1
        return str(1 - int(self.findKthBit(n - 1, mirrored)))

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one level of recursion per halving of the position space.
💾 Space Complexity
O(n): the recursion depth.

⚠️ Interview Pitfalls & Follow-ups

  • Building S_n explicitly: it has about 10^6 characters at n = 20; feasible but wasteful when the recursion is O(n).
  • Using the wrong mirror formula: the mirror of position k in a string of length L is L - k + 1.
  • Forgetting to invert on the right half: that half is the reversed inverse of the left half, so the bit flips.
  • Off-by-one on the middle: the middle index is 2^(n-1), not 2^n / 2 computed with floats.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Bit Manipulation Problems