Find Kth Bit in Nth Binary String

Problem Statement

In this task, given two positive integers n and k, we need to create a sequence of binary strings based on n and determine the k-th bit in the n-th string of that sequence. The sequence of binary strings, S1, S2, S3, ... Sn, is constructed through a specific set of operations:

• S1 is initialized to the string "0".
• Any subsequent Si for i > 1 is created by concatenating three segments:
  1. The string Si-1.
  2. The string "1".
  3. The inverted and reversed version of Si-1.

For concatenation, we join two strings end-to-end. The reverse(x) operation reverses the order of bits in the string x, while the invert(x) function flips all the bits in the string, changing 0 to 1 and vice versa. From the generated string Sn, the objective is to find out what the bit at position k is.

Examples

Example 1

Input:

n = 3, k = 1

Output:

"0"

Explanation:

S3 is "0111001".
The 1st bit is "0".

Example 2

Input:

n = 4, k = 11

Output:

"1"

Explanation:

S4 is "011100110110001".
The 11th bit is "1".

Constraints

• 1 <= n <= 20
• 1 <= k <= 2n - 1

Approach and Intuition

Given the structure of the problem, the approach revolves around understanding how the strings Sn are constructed and efficiently determining the k-th bit without necessarily building the entire string Sn, especially since these strings grow exponentially in length. Below is a breakdown of the approach based on given examples and constraints:

1. Understanding Sn construction: Each string in the sequence is built using a previous string. Starting from a base, each subsequent string is larger and derived from complex operations on all prior content. Thus, understanding the exact length and composition of strings quickly becomes intractable if done naively for large n.

2. Recursive Relations:

   • We know that the middle bit of Si for i>1 is always 1.
   • We know that the first half of Si (except the middle bit) is the same as Si-1.
   • The second half (after the middle bit) of Si is the reversed and inverted Si-1.

   Using these properties can lead to a recursive determination of any bit's value in Si without explicit string construction:

   • If the desired bit k is the middle bit of Si, it’s 1.
   • If k is in the first half (excluding the middle bit), the problem reduces to finding the k-th bit in Si-1.
   • If k is in the second half, the problem translates to finding a corresponding bit in Si-1 and then inverting it.

3. Optimal Tracking of k:

   • Knowing the length of each Si (which is 2^i - 1), allows calculation of whether k falls before, at, or after the middle bit.
   • Using recursive insight, adjust k and i accordingly to find the bit either directly or via inversion.

This methodology allows us to efficiently trace back through the recursive structure without needing exponential space or time, as direct computation would entail, making it feasible given the constraints.

Solutions

class Solution {
public:
    char findKthBit(int n, int k) {
        int bitPosition = k & -k;
        bool isFlipSection = ((k / bitPosition) >> 1 & 1) == 1;
        bool isFirstBitOne = (k & 1) == 0;
    
        if (isFlipSection) {
            return isFirstBitOne ? '0' : '1';
        } else {
            return isFirstBitOne ? '1' : '0';
        }
    }
};