Find Kth Bit in Nth Binary String

function findKthBit(n: number, k: number): string {
  let s = '0';
  for (let i = 1; i < n; i++) {
    if (k <= s.length) break;
    s += '1' + reverse(invert(s));
  }
  return s[k - 1];
}
 
function invert(s: string) {
  return [...s].map((bit) => (bit === '0' ? '1' : '0')).join('');
}
 
function reverse(s: string) {
  return [...s].reverse().join('');
}

function findKthBit(n: number, k: number): string {
  if (n === 1) {
    return '0';
  }
  const length = 1 << n;
  if (k < Math.floor(length / 2)) {
    return findKthBit(n - 1, k);
  }
  if (k === Math.floor(length / 2)) {
    return '1';
  }
 
  return findKthBit(n - 1, length - k) === '0' ? '1' : '0';
}

export function findKthBit(n: number, k: number): string {
  let invertCount = 0;
  let totalLength = (1 << n) - 1;
  while (1 < k) {
    const mid = Math.floor(totalLength / 2);
    if (k === mid + 1) {
      return invertCount % 2 === 0 ? '1' : '0';
    }
    if (k > mid) {
      k = totalLength + 1 - k;
      invertCount += 1;
    }
    totalLength = Math.floor(totalLength / 2);
  }
  return invertCount % 2 === 0 ? '0' : '1';
}