Skip to content

1545. Find Kth Bit in Nth Binary String 👍

  • Time: $O(n^2)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
 public:
  char findKthBit(int n, int k) {
    if (n == 1)
      return '0';
    const int midIndex = pow(2, n - 1);  // 1-indexed
    if (k == midIndex)
      return '1';
    if (k < midIndex)
      return findKthBit(n - 1, k);
    return findKthBit(n - 1, midIndex * 2 - k) == '0' ? '1' : '0';
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
  public char findKthBit(int n, int k) {
    if (n == 1)
      return '0';
    final int midIndex = (int) Math.pow(2, n - 1); // 1-indexed
    if (k == midIndex)
      return '1';
    if (k < midIndex)
      return findKthBit(n - 1, k);
    return findKthBit(n - 1, midIndex * 2 - k) == '0' ? '1' : '0';
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
  def findKthBit(self, n: int, k: int) -> str:
    if n == 1:
      return '0'
    midIndex = pow(2, n - 1)  # 1-indexed
    if k == midIndex:
      return '1'
    if k < midIndex:
      return self.findKthBit(n - 1, k)
    return '1' if self.findKthBit(n - 1, midIndex * 2 - k) == '0' else '0'