Solution For Find Kth Bit In Nth Binary String

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 = 2length – 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).

Step by Step Implementation For Find Kth Bit In Nth Binary String

class Solution {
    public char findKthBit(int n, int k) {
        StringBuilder s = new StringBuilder("0");
        for (int i = 2; i <= n; i++) {
            StringBuilder cur = new StringBuilder();
            cur.append(s);
            cur.append("1");
            for (int j = s.length() - 1; j >= 0; j--) {
                cur.append(s.charAt(j) == '1' ? '0' : '1');
            }
            s = cur;
        }
        return s.charAt(k - 1);
    }
}

def findKthBit(n, k): 

# Edge case if n = 1 

if n == 1: 

return "0"

# Base case if n = 2 

if n == 2: 

if k == 1: 

return "0"

else: 

return "1"

# If k is equal to the length of the string + 1, 

# that means we need to invert the last bit 

if k == (2 ** (n - 1)) + 1: 

return flip(findKthBit(n - 1, k - (2 ** (n - 2))))

# If k is less than the length of the string, 

# that means the bit we are looking for is in 

# the first half of the string 

elif k <= (2 ** (n - 2)): 

return findKthBit(n - 1, k)

# Otherwise, the bit we are looking for is in the 

# second half of the string 

else: 

return findKthBit(n - 1, k - (2 ** (n - 2)))

# Function to invert a binary string 

def flip(string): 

inverted = "" 

for bit in string: 

if bit == "0": 

inverted += "1"

else: 

inverted += "0"

return inverted

var findKthBit = function(n, k) {
  // create an array to store all the binary strings
  let arr = [];
  // create a variable to store the current binary string
  let curr = "0";
  // loop through n
  for (let i = 0; i < n; i++) {
    // add the current binary string to the array
    arr.push(curr);
    // create a variable to store the next binary string
    let next = "";
    // loop through the current binary string
    for (let j = 0; j < curr.length; j++) {
      // if the current character is a "0"
      if (curr[j] === "0") {
        // add a "1" to the next binary string
        next += "1";
      }
      // if the current character is a "1"
      else {
        // add a "0" to the next binary string
        next += "0";
      }
    }
    // reverse the next binary string
    next = next.split("").reverse().join("");
    // add a "1" to the end of the next binary string
    next += "1";
    // set the current binary string to the next binary string
    curr = next;
  }
  // return the character at index k - 1 of the last binary string in the array
  return arr[n - 1][k - 1];
};

class Solution {
public:
    char findKthBit(int n, int k) {
        // If n is 1, the only possible k is 1, and the answer is 0.
        if (n == 1) return '0';
        
        // If k is equal to the length of the nth binary string,
        // the answer is the last bit of the string, which is always 1.
        int len = (1 << n) - 1;
        if (k == len) return '1';
        
        // If k is less than the length of the nth binary string,
        // we can find the answer by reversing the bits to the left of k
        // in the (n - 1)th binary string and then concatenating it with
        // the nth binary string.
        if (k < len) {
            string s = findKthBit(n - 1, len - k);
            for (int i = 0; i < s.length(); ++i) {
                s[i] = (s[i] == '0' ? '1' : '0');
            }
            return s + '1';
        }
        
        // Otherwise, k must be greater than the length of the nth binary string,
        // so we can find the answer by reversing the bits to the right of k
        // in the (n - 1)th binary string and then concatenating it with
        // the nth binary string.
        string s = findKthBit(n - 1, k - len);
        for (int i = 0; i < s.length(); ++i) {
            s[i] = (s[i] == '0' ? '1' : '0');
        }
        return s + '0';
    }
};

class Solution {
    public char findKthBit(int n, int k) {
        // TODO: Implement your solution here
    }
}