leetcode

commit 6f4ebe95ad9890f3ed441ff4d037f2c63be0888a
parent bb6ec1474604288c2d081fe4d5d82f01570a64ff
Author: Jack Sangdahl <jack@pngu.org>
Date:   Mon,  2 Mar 2026 21:24:47 -0700

1545. find kth bit in nth binary string

Diffstat:
M
find_kth_bit_nth_bin_str.c
 | 
27
+++++++++++++--------------
M
find_kth_bit_nth_bin_str.py
 | 
20
+++-----------------

2 files changed, 16 insertions(+), 31 deletions(-)
diff --git a/find_kth_bit_nth_bin_str.c b/find_kth_bit_nth_bin_str.c
@@ -9,22 +9,21 @@
  * k'th bit in 's_n'. it is guaranteed that 'k' is valid for the given 'n'.
  */
 
-int max_bit(int n) {
-  while ((n & (n - 1)))
-    n &= n - 1;
-  return n;
-}
-
 char findKthBit(int n, int k) {
-  int inv = 0;
-  while (k & (k - 1)) {
-    k = -k & (max_bit(k) - 1);
-    inv ^= 1;
-  }
-  return ((k > 1) ^ inv) + '0';
+  if (k == 1)
+    return '0';
+  int m = 32 - __builtin_clz(k);
+  int x = (1 << m) - k;
+  if (x == k)
+    return '1';
+  return findKthBit(n, x) == '0' ? '1' : '0';
 }
 
 int main() {
-  printf("%c\n", findKthBit(3, 1));  // expect: 0
-  printf("%c\n", findKthBit(4, 11)); // expect: 1
+  char r1 = findKthBit(3, 1);
+  char r2 = findKthBit(4, 11);
+  printf("%c\n", r1); // expect: 0
+  assert(r1 == '0');
+  printf("%c\n", r2); // expect: 1
+  assert(r2 == '1');
 }
diff --git a/find_kth_bit_nth_bin_str.py b/find_kth_bit_nth_bin_str.py
@@ -9,23 +9,9 @@ k'th bit in 's_n'. it is guaranteed that 'k' is valid for the given 'n'.
 """
 
 
-class Solution(object):
-    def findKthBit(self, n, k):
-        """
-        :type n: int
-        :type k: int
-        :rtype: str
-        """
-        flip = 0
-        inv = 2**n - 1
-        while k > 1:
-            if k == inv / 2 + 1:
-                return str(1 ^ flip)
-            if k > inv / 2:
-                k = inv + 1 - k
-                flip = 1 - flip
-            inv /= 2
-        return str(flip)
+class Solution:
+    def findKthBit(self, n: int, k: int) -> str:
+        return str(k // (k & -k) >> 1 & 1 ^ k & 1 ^ 1)
 
 
 if __name__ == "__main__":