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:

1. 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 string Si-1, a “1”, and the reverse of Si-1 with all bits inverted.
   • We recursively generate the previous string until we reach S1.

2. 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"