Problem

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 = "0**1**1"
  • S3 = "011**1**001"
  • S4 = "0111001**1**0110001"

Return the kth bit in Sn. It is guaranteed that k is valid for the given n.

Examples

Example 1:

1
2
3
4

Input: n = 3, k = 1
Output: "0"
Explanation: S3 is "**0**111001".
The 1st bit is "0".

Example 2:

1
2
3
4

Input: n = 4, k = 11
Output: "1"
Explanation: S4 is "0111001101**1**0001".
The 11th bit is "1".

Solution

Method 1 - Using recursion

Given the nature of how the binary strings S_n are generated recursively, explicitly constructing the strings up to S_n would be inefficient for larger values of n.

Each binary string is formed recursively by inserting a “1” in the middle and appending an inverted and reversed version of the previous string. So, by understanding the structure and recursive generation of the strings, we can determine the k-th bit efficiently using recursion or iteration. The recursive relationship allows us to bypass the need to generate the entire string and directly find the k-th bit by:

  1. Identifying the midpoint.
  2. Determining the position of k relative to the midpoint.
  3. Using the properties of inversion and reversal.

Approach

Here is the approach:

  1. Recursive Structure:
    • Each string S_n is derived from the previous string S_{n-1} by appending 1 and the reversed inverted version of S_{n-1}.
    • Key observations:
      • The midpoint of S_n is at index 2^(n-1).
      • The structure of each part is symmetric.
  2. Base Case:
    • If n = 1, the string is "0".
  3. Recursion:
    • If k equals the midpoint, return 1.
    • If k lies in the first half, recursively find the bit in S_{n-1}.
    • If k lies in the second half, find the corresponding position in the first half of S_{n-1}, compute the bit, and then invert it.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    public char findKthBit(int n, int k) {
        // Base case: When n is 1, S1 is "0"
        if (n == 1) {
            return '0';
        }
        
        // Calculate the length of Sn, which is 2^n - 1
        int length = (1 << n) - 1; // Equivalent to Math.pow(2, n) - 1
        // Calculate the midpoint position
        int mid = (length / 2) + 1;
        
        // If k is the midpoint, the k-th bit is always '1'
        if (k == mid) {
            return '1';
        } 
        // If k is in the first half, recursively find the bit in Sn-1
        else if (k < mid) {
            return findKthBit(n - 1, k);
        } 
        // If k is in the second half
        else {
            // Find the equivalent position in the first half and invert the result
            int mirrored_pos = mid - (k - mid);
            return findKthBit(n - 1, mirrored_pos) == '0' ? '1' : '0';
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        if n == 1:
            return '0'
        
        length = 2 ** n - 1
        mid = length // 2 + 1
        
        if k == mid:
            return '1'
        elif k < mid:
            return self.findKthBit(n - 1, k)
        else:
            # Find the equivalent position in the first half and invert
            mirrored_pos = mid - (k - mid)
            return '1' if self.findKthBit(n - 1, mirrored_pos) == '0' else '0'

Complexity

  • ⏰ Time complexity: O(n),  because each recursive call reduces the size by half.
  • 🧺 Space complexity: O(n), due to recursion stack.