Problem Description

You need to find the k-th bit in a special binary string S_n that is constructed using a recursive pattern.

The binary strings are built following these rules:

• S₁ = "0" (base case)
• For i > 1: S_i = S_{i-1} + "1" + reverse(invert(S_{i-1}))

Where:

• + means string concatenation
• reverse(x) reverses the string x
• invert(x) flips all bits (0 becomes 1, 1 becomes 0)

For example, here's how the first four strings are constructed:

• S₁ = "0"
• S₂ = "0" + "1" + reverse(invert("0")) = "0" + "1" + reverse("1") = "0" + "1" + "1" = "011"
• S₃ = "011" + "1" + reverse(invert("011")) = "011" + "1" + reverse("100") = "011" + "1" + "001" = "0111001"
• S₄ = "0111001" + "1" + reverse(invert("0111001")) = "0111001" + "1" + "0110001" = "011100110110001"

Given two positive integers n and k, you need to return the k-th bit (1-indexed) in the string S_n. The problem guarantees that k is a valid position in S_n.

The solution uses a recursive approach by recognizing that:

• Each S_n has length 2^n - 1
• The middle bit is always "1" (at position 2^(n-1))
• The first half (before the middle) is identical to S_{n-1}
• The second half (after the middle) is the reverse and inversion of S_{n-1}

This pattern allows us to recursively determine any bit's value without constructing the entire string.

Intuition

Let's first observe the pattern in how these strings are constructed. Each string S_n follows the pattern: S_{n-1} + "1" + reverse(invert(S_{n-1})). This creates a symmetric structure with a "1" in the middle.

Looking at the lengths:

• S₁ has length 1 = 2^1 - 1
• S₂ has length 3 = 2^2 - 1
• S₃ has length 7 = 2^3 - 1
• S₄ has length 15 = 2^4 - 1

So S_n has length 2^n - 1. The middle position is always at index 2^(n-1), and this position always contains "1".

The key insight is that we don't need to build the entire string to find the k-th bit. Instead, we can use the recursive structure to navigate directly to the position we need:

1. If k = 1: The first bit is always "0" (since S₁ = "0" and every subsequent string starts with the previous string).

2. If k is a power of 2: These positions correspond to the middle "1" bits added at each level of construction. For example, position 2 in S₂, position 4 in S₃, position 8 in S₄, etc.

3. If k is in the first half (k < 2^(n-1)): The first half of S_n is exactly S_{n-1}, so we can recursively find the k-th bit in S_{n-1}.

4. If k is in the second half (k > 2^(n-1)): The second half is reverse(invert(S_{n-1})). To find the corresponding position in S_{n-1}, we need to:

   • Map k to its mirror position in S_{n-1}: position 2^n - k
   • Since it's inverted, we flip the bit we find (XOR with 1)

This recursive approach allows us to "zoom in" on the exact bit we need without constructing the entire string, making it very efficient. Each recursive call reduces the problem size by examining which half of the string contains our target position, similar to binary search.

Learn more about Recursion patterns.

Solution Approach

The solution implements a recursive function dfs(n, k) that returns the k-th bit in string S_n without constructing the entire string.

Core Algorithm:

The function handles four distinct cases based on the position k:

1. Base Case (k = 1):

   • Return 0 directly since every S_n starts with "0"

2. Power of 2 Check ((k & (k - 1)) == 0):

   • This bit manipulation trick checks if k is a power of 2
   • Powers of 2 represent the middle "1" bits added at each construction level
   • Return 1 for these positions

3. First Half Check (k * 2 < m - 1 where m = 1 << n = 2^n):

   • Since S_n has length 2^n - 1, the middle position is at 2^(n-1)
   • If k * 2 < 2^n - 1, then k is in the first half
   • The first half is identical to S_{n-1}, so recursively call dfs(n - 1, k)

4. Second Half (remaining cases):

   • The second half is reverse(invert(S_{n-1}))
   • To find the corresponding position in S_{n-1}, calculate the mirror position: 2^n - k
   • Since the bit is inverted in the second half, XOR the result with 1: dfs(n - 1, m - k) ^ 1

Implementation Details:

• m = 1 << n efficiently calculates 2^n using bit shifting
• (k & (k - 1)) == 0 is a classic bit manipulation to check if k is a power of 2
  • For powers of 2, only one bit is set, so subtracting 1 flips all lower bits
  • ANDing with the original number gives 0 only for powers of 2
• The XOR operation (^ 1) flips the bit: 0 becomes 1, and 1 becomes 0

Time Complexity: O(n) - At most n recursive calls since we reduce n by 1 in each call

Space Complexity: O(n) - Recursion stack depth is at most n

The final answer is converted to string format using str(dfs(n, k)) before returning.

Example Walkthrough

Let's find the 5th bit in S₃ = "0111001" using our recursive approach.

Step 1: Initial call - dfs(3, 5)

• Check if k = 1? No (k = 5)
• Check if k is power of 2? No (5 & 4 = 4, not 0)
• Calculate m = 1 << 3 = 8
• Check if in first half: 5 * 2 = 10, compare with 8 - 1 = 7
• Since 10 > 7, k = 5 is in the second half

Step 2: Map to mirror position in S₂

• Since k is in the second half of S₃, we need to find its mirror in S₂
• Mirror position = m - k = 8 - 5 = 3
• Call dfs(2, 3) ^ 1 (XOR with 1 because second half is inverted)

Step 3: Recursive call - dfs(2, 3)

• Check if k = 1? No (k = 3)
• Check if k is power of 2? No (3 & 2 = 2, not 0)
• Calculate m = 1 << 2 = 4
• Check if in first half: 3 * 2 = 6, compare with 4 - 1 = 3
• Since 6 > 3, k = 3 is in the second half

Step 4: Map to mirror position in S₁

• Mirror position = m - k = 4 - 3 = 1
• Call dfs(1, 1) ^ 1

Step 5: Base case - dfs(1, 1)

• k = 1, so return 0 (first bit is always 0)

Step 6: Backtrack with inversions

• dfs(1, 1) returns 0
• dfs(2, 3) returns 0 ^ 1 = 1
• dfs(3, 5) returns 1 ^ 1 = 0

Verification: S₃ = "0111001", and the 5th bit (1-indexed) is indeed '0'.

The algorithm correctly navigated through the recursive structure without building the entire string, using the symmetry and inversion properties to find the exact bit value.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the given parameter in the problem.

The recursive function dfs makes at most one recursive call per level, and the recursion depth is bounded by n. At each recursive call, the operations performed are constant time:

• Checking if k == 1: O(1)
• Checking if (k & (k - 1)) == 0 to determine if k is a power of 2: O(1)
• Computing m = 1 << n: O(1)
• Comparison k * 2 < m - 1: O(1)
• The recursive calls either decrease n by 1 or maintain the same recursion path

Since we make at most n recursive calls (decreasing n by 1 each time until we reach a base case), and each call performs O(1) work, the total time complexity is O(n).

The space complexity is O(n) due to the recursion call stack. In the worst case, the recursion depth can reach n levels deep (when we keep recursing with n-1), and each recursive call adds a constant amount of space to the call stack. Therefore, the space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in Middle Position Calculation

Pitfall: A common mistake is incorrectly identifying whether a position is in the first or second half of the string. Developers often confuse the middle position calculation or use incorrect comparison operators.

Incorrect Implementation:

# Wrong: Using <= instead of <
if position * 2 <= string_length - 1:  # This incorrectly includes the middle position
    return find_bit_recursive(level - 1, position)

# Wrong: Incorrect middle position calculation
middle = (1 << level) // 2  # This gives 2^(level-1), not the actual middle position
if position < middle:
    return find_bit_recursive(level - 1, position)

Solution: The correct approach uses position * 2 < string_length - 1 to check if a position is in the first half. This works because:

• The string S_n has length 2^n - 1
• The middle position is at 2^(n-1) (which is (2^n - 1 + 1) / 2)
• If k * 2 < 2^n - 1, then k is strictly before the middle

2. Incorrect Power of 2 Check

Pitfall: Using inefficient or incorrect methods to check if a number is a power of 2.

Incorrect Implementation:

# Wrong: This checks if position equals 2^(level-1), missing other power of 2 positions
if position == (1 << (level - 1)):
    return 1

# Inefficient: Using logarithm (can have floating-point precision issues)
import math
if math.log2(position) == int(math.log2(position)):
    return 1

Solution: Use the bitwise trick (position & (position - 1)) == 0. This works because:

• Powers of 2 have exactly one bit set (e.g., 8 = 1000 in binary)
• Subtracting 1 flips all bits after the single set bit (e.g., 7 = 0111)
• ANDing them gives 0 only for powers of 2

3. Forgetting to Invert Bits in Second Half

Pitfall: When handling positions in the second half, forgetting that the bits are both reversed AND inverted.

Incorrect Implementation:

# Wrong: Only reversing without inverting
if position * 2 >= string_length:
    mirrored_position = string_length - position
    return find_bit_recursive(level - 1, mirrored_position)  # Missing XOR 1

Solution: Always remember to XOR with 1 when dealing with the second half: return find_bit_recursive(level - 1, mirrored_position) ^ 1

4. Using 0-Indexed Instead of 1-Indexed Positions

Pitfall: The problem uses 1-indexed positions, but developers might accidentally use 0-indexed logic.

Incorrect Implementation:

def findKthBit(self, n: int, k: int) -> str:
    # Wrong: Converting to 0-indexed but forgetting to adjust back
    k = k - 1  # Convert to 0-indexed
    result = find_bit_recursive(n, k)  # But the recursive function expects 1-indexed!
    return str(result)

Solution: Keep the position 1-indexed throughout the recursive function, as the base case if position == 1: return 0 relies on 1-indexing.