1545.js

/** ------------------------------------------------------------------------------
 * 
 * 1545. Find Kth Bit in Nth Binary String
 * Topics: Bit
 * https://leetcode.com/problems/find-kth-bit-in-nth-binary-string/description/?envType=daily-question&envId=2024-10-19
 * 
 ------------------------------------------------------------------------------ */
var findKthBit = function (n, k) {
  if (k === 1) return "0"
  if (k === 2) return "1"

  let binary = 2
  while (binary < k) {
    binary *= 2
  }

  let count = 0
  while (binary > 2) {
    if (k == binary / 2) {
      return count % 2 == 0 ? "1" : "0"
    }
    if (k > binary / 2) {
      k = binary - k
      count++
    }
    binary /= 2
  }

  return count % 2 == 0 ? "0" : "1"
}

var findKthBit = function (n, k) {
  if (n === 1) return "0"

  const mid = (1 << (n - 1)) - 1

  if (k <= mid) {
    return findKthBit(n - 1, k)
  } else if (k === mid + 1) {
    return "1"
  } else {
    return findKthBit(n - 1, (1 << n) - k) === "0" ? "1" : "0"
  }
}