1545. Find Kth Bit in Nth Binary String

[mah-shamim]

Topics: String, Recursion, Simulation

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 = "011"
• S3 = "0111001"
• S4 = "011100110110001"

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

Example 1:

• Input: n = 3, k = 1
• Output: "0"
• Explanation: S₃ is "0111001".
  The 1^st bit is "0".

Example 2:

• Input: n = 4, k = 11
• Output: "1"
• Explanation: S₄ is "011100110110001".
  The 11^th bit is "1".

Example 3:

• Input: n = 3, k = 2
• Output: "0"

Constraints:

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

Hint:

1. Since n is small, we can simply simulate the process of constructing S1 to Sn.

[kovatz]

We need to understand the recursive process used to generate each binary string Sn and use this to determine the k-th bit without constructing the entire string.

Approach:

1. Recursive String Construction:

   • S₁ = "0".
   • For i > 1:
     • Si is constructed as:
       
Si = Si-1 + "1" + reverse(invert(Si-1))

   • This means S_i consists of three parts:
     • S_i-1 (the original part)
     • "1" (the middle bit)
     • reverse(invert(S_i-1)) (the transformed part)

2. Key Observations:

   • S_i has a length of 2^i-1.
   • The middle bit (position 2^i-1 of S_i is always "1".
   • If k lies in the first half, it falls within S_i-1.
   • If k is exactly the middle position, the answer is "1".
   • If k is in the second half, it corresponds to the reverse-inverted part.

3. Inverting and Reversing:

   • To determine the bit in the second half, map k to its corresponding position in the first half using:
     
k' = 2i - k

   • The bit at this position in the original half is inverted, so we need to flip the result.

4. Recursive Solution:

   • Recursively determine the k-th bit by reducing n and mapping k until n = 1.

Let's implement this solution in PHP: 1545. Find Kth Bit in Nth Binary String

<?php
/**
 * @param Integer $n
 * @param Integer $k
 * @return String
 */
function findKthBit($n, $k) {
    if ($n == 1) {
        return "0";
    }

    $mid = (1 << ($n - 1)); // 2^(n-1)

    if ($k == $mid) {
        return "1";
    } elseif ($k < $mid) {
        return findKthBit($n - 1, $k);
    } else {
        $result = findKthBit($n - 1, $mid * 2 - $k);
        return $result === "0" ? "1" : "0"; // Flip the bit
    }
}
?>

Explanation:

• Base Case: If n = 1, S_i is "0", so the only possible value for any k is "0".
• Recursive Steps:
  • Calculate the middle index mid which is 2^n-1.
  • If k matches the middle index, return "1".
  • If k is less than mid, the k-th bit lies in the first half, so we recursively find the k-th bit in S_n-1.
  • If k is greater than mid, we find the corresponding bit in the reverse-inverted second half and flip it.

Complexity Analysis:

• Time Complexity: O(n) because each recursive call reduces n by 1.
• Space Complexity: O(n) for the recursive call stack.

Example Walkthrough:

1. Input: n = 3 , k = 1

   • S₃ = "0111001"
   • k = 1 falls in the first half, so we look for k = 1 in S₂.
   • In S₂ = "011" , k = 1 corresponds to "0".

2. Input: n = 4 , k = 11

   • S₄ = "011100110110001"
   • The middle index for S₄ is 8.
   • k = 11 falls in the second half.
   • Map k = 11 to the corresponding bit in the first half: k' = 2^{4 - 11 = 5}.
   • Find k = 5 in S₃ , which is "0", then flip it to "1".

By leveraging recursion and properties of the string construction, this solution avoids generating the entire string, making it efficient even for larger n.

[mah-shamim]

Thanks to solve the "Find Kth Bit in Nth Binary String" problem

[kovatz]

Thanks