Find Kth Bit In Nth Binary String - Leetcode Solution

Problem:

Given two positive integers n and k, the task is to find the kth bit in the nth binary string.

The binary strings are arranged in the following order: First, all the binary strings whose length is 1 are listed, followed by all the binary strings whose length is 2, and so on. For example, the first 5 binary strings are "0", "1", "00", "01", and "10".

Solution:

Approach:

The main idea behind solving this problem is to determine the length of the binary string containing the Kth bit. Once the length of the binary string is determined we can find the first bit in the binary string, and then recursively go on to find the kth bit in the remaining binary string.

Algorithm:

1. Initialize a variable len as 1.
2. While k is greater than 2 raised to len - 1, increment len
3. If k is less than or equal to 2 raised to len - 1 divided by 2, the first bit of the nth binary string is 0, otherwise it is 1.
4. If the first bit is 0, recursively find the kth bit in the binary string of length len - 1 and kth bit position k.
5. If the first bit is 1, recursively find the (k - 2 raised to len - 1 divided by 2)th bit in the binary string of length len - 1 and kth bit position k.

Complexity Analysis:

Time Complexity: O(log n). The while loop for finding the length of the binary string takes O(log n) time.

Space Complexity: O(1). No extra space is required in this approach.

Note: The binary strings in this problem are arranged in lexical order. We can use the following code to implement this approach in Python.

Code:

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        length = 1
        while k > 2**(length-1):
            k = 2**length - k
            length += 1
        
        def recurse(n, k):
            if n == 1:
                return "0"
            
            middle = 2**(n - 1)
            if k == middle:
                return "1"
            elif k < middle:
                return recurse(n - 1, k)
            else:
                return str(1 - int(recurse(n - 1, middle - (k - middle))))
        
        return recurse(length, k)

Explanation:

Initially, we initialize a variable length as 1 as the binary strings of length 1 comes first and we traverse according to the length.

The while loop checks that k is greater than or equal to 2 raised to length-1. In each iteration of the loop, if the value of k is greater, we increment the value of length by 1 and calculate the new value of k and decrease the value of k by 2 raised to length minus 1 to start over counting again from 1. We do not need to store the binary string and need to calculate only the Kth bit, thus decreasing redundancy.

After the values of length and the new value of k are calculated, we define a recursive function recurse(n, k) that takes as arguments the length of the binary string, n and the position of the kth bit that needs to be determined.

Before making the recursive call, we need to check whether the kth bit lies on the first half or the second half of the string. We can do this by comparing the middle point (2 raised to n minus 1) and the value of k.

If the middle point is equal to k, it means that the kth bit is a 1 in that string and the function returns 1.

If k is less than the middle point, the kth bit lies in the first half of the string, so we make a recursive call with n minus 1 as the length of the binary string and k as the position of the bit we are looking for.

If k is greater than the middle point, the kth bit lies in the second half of the string. In this case, the first bit of the string is a 1, and we need to flip the bit found at the (k - middle) position in the string of length n minus 1. Thus, we make a recursive call with n minus 1 as the length of the binary string and middle minus (k - middle) as the position of the bit we are looking for.

At last, we return the value obtained from the my_function recurse(length, k).

1