Problem Analysis

Given an integer n, a binary string sequence is defined where:

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

The task is to find the k-th character in Sn.

Key Observations

Examining the pattern reveals a recursive structure:

• S1 has length 1
• S2 has length 3
• S3 has length 7
• In general, |Sn| = 2^n - 1

The middle character of each string is always "1". This symmetry suggests a divide-and-conquer approach rather than constructing full strings.

Recursive Solution

For any position k in Sn:

• If k is at the midpoint: return "1"
• If k is in the left half: return the result for position k in Sn-1
• If k is in the right half: invert the result for position (2^n - 1) - k in Sn-1

var findKthBit = function(n, k) {
    if (n === 1) return '0';
    
    const len = Math.pow(2, n) - 1;
    const mid = Math.ceil(len / 2);
    
    if (k === mid) return '1';
    
    if (k < mid) {
        return findKthBit(n - 1, k);
    }
    
    // k > mid: look up in the inverted right half
    const mirrorPos = len - k + 1;
    const leftResult = findKthBit(n - 1, mirrorPos);
    return leftResult === '0' ? '1' : '0';
};

Bit Inversion Considerations

The inversion operation (0 → 1, 1 → 0) can be implemented in several ways:

// Approach 1: Conditional logic
const invert1 = (c) => c === '0' ? '1' : '0';

// Approach 2: Character mapping
const invert2 = (c) => String.fromCharCode(c.charCodeAt(0) ^ 1);

// Approach 3: Map over string
const invert3 = (str) => str.split('').map(c => c ^ 1).join('');

Important note on XOR with strings:

Direct string XOR like "0100" ^ "1111" produces unexpected numeric results due to JavaScript's type coercion. XOR operations work correctly only on single characters:

'0' ^ 1  // returns 1
'1' ^ 1  // returns 0

When inverting multiple characters, the string must first be split in to characters, each XOR'd individually, then rejoined.

Complexity Analysis

• Time complexity: O(n) — the recursion depth is n, and each level performs O(1) work
• Space complexity: O(n) — recursion stack depth

Iterative Alternative

An iterative approach using a loop:

var findKthBit = function(n, k) {
    let result = '0';
    
    for (let i = 2; i <= n; i++) {
        const len = Math.pow(2, i) - 1;
        const mid = Math.ceil(len / 2);
        
        if (k === mid) return '1';
        
        if (k > mid) {
            k = len - k + 1;
            result = result === '0' ? '1' : '0';
        }
    }
    
    return result;
};

This iterative version tracks the position in the mirrored left portion and flips the final result when crossing into the right half.