Leetcode Daily Question 19/10/2024 - 1545. Find Kth Bit in Nth Binary String

Problem Description:

Given two positive integers n and k, the binary string Sn is formed as follows: | ---------------------------------------------------------- | S1 = "0" Si = Si - 1 + "1" + reverse(invert(Si - 1)) for i > 1 Where + denotes the concatenation operation, reverse(x) returns the reversed string x, and invert(x) inverts all the bits in x (0 changes to 1 and 1 changes to 0). | ---------------------------------------------------------- | For example, the first four strings in the above sequence are: | ---------------------------------------------------------- | S1 = "0"; S2 = "011"; S3 = "0111001"; S4 = "011100110110001" | ---------------------------------------------------------- | Return the kth bit in Sn. It is guaranteed that k is valid for the given n.

class Solution:
  def findKthBit(self, n: int, k: int) -> str:
    def recursion(n: int, k: int):
      if n == 1:
        return "0"
      prev_s_len = (1 << n - 1) - 1
      mid = prev_s_len + 1
      
      if k == mid:
        return "1"
      elif k < mid:
        return recursive(n - 1, k)
      else:
        invert_pos = 2 * prev_s_len + 2 - k
        bit = recursive(n - 1, invert_pos)
        return "0" if bit == "1" else "1"
    return recursive(n, k)

Explanation:

We can solve the problem using recursion by breaking down the structure of the string into smaller parts, allowing us to find the character at index k-1 without fully constructing the string.

At each recursion step, we know that the string S_n follows a specific structure:

S_n = S_(n-1) + "1" + reverse(invert(S_(n-1))).

This means:

S_(n-1) is the first part of the string, which has a length of 2^(n-1) - 1.

Then, there is the middle "1", positioned at index 2^(n-1).

Finally, the last part is the reverse and inverted form of S_(n-1).

-

With this structure, we can locate where k lies:

If k is in the first part, it belongs to S_(n-1).

If k matches the middle position (index 2^(n-1)), the result is "1".

If k is in the second half, it corresponds to a position in the reverse-inverted part of S_(n-1).

We recursively reduce the problem by calling the function on the smaller string S_(n-1) and adjusting k accordingly. This approach allows us to avoid building the entire string, making the solution much more efficient.

def recursion(n, k):
  if n == 1:
    return "0"
  
  prev_s_last_index = 2 ^ (n - 1) - 1
  mid = prev_s_last_index + 1
  
  if k == mid:
    return "1"
  elif k < mid:
    return recursion(n - 1, k)
  else:
    inverted_pos = 2 * prev_s_last_index + 2 - k
    bit = recursion(n - 1, inverted_pos)
    return "0" if bit == "1" else "1"

return recursion(n, k)

The time complexity is O(n). Although we do not generate the entire string. We make one recursive call per level. So the time complexity is proportional to O(n).

The space complexity is O(1) as we only store constant variables.

The full solution can be found near the top of the page.