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
- The length of
S_nis2^n - 1, and its middle position2^(n-1)is always1. - If
kis the middle position, the answer is1without any recursion. - If
klies in the left half, it is thek-th bit ofS_{n-1}. - If
klies in the right half, it mirrors positionlength - k + 1of 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_nexplicitly: it has about 10^6 characters atn = 20; feasible but wasteful when the recursion is O(n). - Using the wrong mirror formula: the mirror of position
kin a string of lengthLisL - 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), not2^n / 2computed with floats.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.