Problem of The Day: Find Kth Bit in Nth Binary String
Problem Statement
Intuition
The problem can be understood as generating a recursive sequence of strings, where each string is constructed based on the previous one by inverting the characters of the previous string and appending it in reverse with a ‘1’ in the middle. Our goal is to efficiently construct this sequence and retrieve the k-th bit in the n-th string.
Approach
The approach involves two main tasks:
-
Recursive String Generation:
- We define a helper function
helper(n)
to generate the n-th string in the sequence. The first string,S1
, is simply “0”. - For each subsequent string
Si
, we generate it by concatenating the previous stringSi-1
, a “1”, and the reverse ofSi-1
with all bits inverted. - We recursively generate the previous string until we reach
S1
.
- We define a helper function
-
Finding the k-th Bit:
- Once the n-th string is generated using the helper function, we directly access the k-th bit by indexing into the string (adjusted for 0-based indexing).
Complexity
-
Time complexity:
- The time complexity of generating the n-th string recursively is \(O(2^n)\) because at each level, the string doubles in size.
- Finding the k-th bit takes constant time \(O(1)\) once the string is generated.
- Thus, the overall time complexity is \(O(2^n)\).
-
Space complexity:
- The space complexity is also \(O(2^n)\), due to the storage of the generated string and the recursive function stack.
Code
class Solution:
def helper(self, n):
if n == 1:
return '0'
s_i = self.helper(n - 1)
s_i_invert = []
for x in s_i:
if x == '1': s_i_invert.append('0')
else: s_i_invert.append('1')
return s_i + "1" + ''.join(reversed(s_i_invert))
def findKthBit(self, n: int, k: int) -> str:
convert_string = self.helper(n)
return convert_string[k - 1]
Editorial
Approach 1: Brute Force
class Solution:
def findKthBit(self, n: int, k: int) -> str:
sequence = "0"
# Generate sequence until we have enough elements or reach nth iteration
for i in range(1, n):
if k <= len(sequence):
break
sequence += "1"
# Append the inverted and reversed part of the existing sequence
inverted = "".join(
"1" if bit == "0" else "0" for bit in sequence[:-1]
)
sequence += inverted[::-1]
# Return the kth bit
return sequence[k - 1]
Approach 2: Recursion
class Solution:
def findKthBit(self, n: int, k: int) -> str:
# Base case: for S1, return '0'
if n == 1:
return "0"
# Calculate the length of Sn
length = 1 << n # Equivalent to 2^n
# If k is in the first half of the string, recurse with n-1
if k < length // 2:
return self.findKthBit(n - 1, k)
# If k is exactly in the middle, return '1'
elif k == length // 2:
return "1"
# If k is in the second half of the string
else:
# Find the corresponding bit in the first half and invert it
corresponding_bit = self.findKthBit(n - 1, length - k)
return "1" if corresponding_bit == "0" else "0"
Approach 3: Iterative Divide and Conquer
class Solution:
def findKthBit(self, n: int, k: int) -> str:
invert_count = 0
len = (1 << n) - 1 # Length of Sn is 2^n - 1
while k > 1:
# If k is in the middle, return based on inversion count
if k == len // 2 + 1:
return "1" if invert_count % 2 == 0 else "0"
# If k is in the second half, invert and mirror
if k > len // 2:
k = len + 1 - k # Mirror position
invert_count += 1 # Increment inversion count
len //= 2 # Reduce length for next iteration
# For the first position, return based on inversion count
return "0" if invert_count % 2 == 0 else "1"