Problem Explanation

This problem asks to find the Kth bit of the Nth string generated by a specific rule.The rule to generate the strings in the sequence is given by:

1S1 = "0"
2Si = Si-1 + "1" + reverse(invert(Si-1)), for i > 1

Where:

• "+" denotes the concatenate operation,
• reverse(x) returns the reversed string x,
• invert(x) inverts all the bits in x (0 changes to 1 and 1 changes to 0).

We are also given that a string Sn is generated from a string Si with three operations: append 1 to the end of Si, append the inverse of the reverse of Si to the end of the result. Our task is to return the kth bit of the resulting string Sn.

Let's take the example where n = 4 and k = 11.

1S1 = "0"
2S2 ("0"+"1"+reverse(invert("0"))) = "0" + "1" + "1" = "011"
3S3 ("011"+"1"+reverse(invert("011"))) = "011" + "1" + "100" = "0111001"
4S4 ("0111001"+"1"+reverse(invert("0111001"))) = "0111001" + "1" + "1001100" = "011100110110001"

The 11th character in the string S4 is 1.

Solution Approach

This is a recursive problem. The base case is when n becomes 1, in which case we return '0', as our first string S1 is "0". If k equals half the length of Sn (which is a valid index due to being 1-indexed), we return '1', because we always add '1' in the middle of Sn.

If k is less than half the length of Sn, we keep searching in the first half of Sn (or equivalently in Sn-1) with the same index k.

If k is more than half the length of Sn, it falls in the second half; we invert our search criteria and continue our search in Sn-1 with the index of the mirrored position.

Solution

Python Solution

1
2python
3class Solution:
4    def findKthBit(self, n: int, k: int) -> str:
5        if n == 1: # Base case
6            return '0'
7        midIndex = pow(2, n - 1) # the middle index
8        if k == midIndex: 
9            return '1'
10        elif k < midIndex: 
11            return self.findKthBit(n - 1, k) # search in the first half
12        else:
13            # search in the second half(inverted and reversed)
14            return '1' if self.findKthBit(n - 1, midIndex * 2 - k) == '0' else '0' 

Java Solution

1
2java
3class Solution {
4    public char findKthBit(int n, int k) {
5        if (n == 1) {
6            return '0';
7        }
8        int midIndex = (int) Math.pow(2, n - 1); 
9        if (k == midIndex) {
10            return '1';
11        } else if (k < midIndex) {
12            return findKthBit(n - 1, k);
13        } else {
14            return findKthBit(n - 1, midIndex * 2 - k) == '0' ? '1' : '0';
15        }
16    }
17}

JavaScript Solution

1
2javascript
3var findKthBit = function(n, k) {
4    if (n === 1) {
5        return '0';
6    }
7    let midIndex = Math.pow(2, n - 1); 
8    if (k === midIndex) {
9        return '1';
10    } else if (k < midIndex) {
11        return findKthBit(n - 1, k);
12    } else {
13        return findKthBit(n - 1, midIndex * 2 - k) === '0' ? '1' : '0';
14    }
15};

In conclusion:

The solution for getting the k-th bit of the string Sn generated from a string Si which was formulated is a recursive method. It starts with checking when n becomes 1(the base case), then checks if k equals half the length of Sn (since 1 is always in the middle of the string Sn). The two separate actions are taken:

• If k is less than half the length, the function keeps searching in the first half of string Sn (equivalent to string Sn-1) at the same index.
• If k is more than half the length, then the action is inverted and the search continues on Sn-1 with the index of the rotated position.

The recursive strategy is applied in this solution during its execution, which aids in reducing the immeasurable length of Sn by dividing it into two halves, checking, and operating on them separately.

The solution code was implemented in three different programming languages - Python, JavaScript, and Java, and each one successfully solves the problem with compatible syntax and tools. The underlying logic and algorithm remain the same, they find the Kth bit of the Nth binary string following the specified rules.