leetcode

commit ec0c54a67a9d545c5173cbefe7ad466a519f3d19
parent 30591a83bd4bb06879d9f490faa0cff6dd77c206
Author: Jack Sangdahl <jack@pngu.org>
Date:   Sat, 21 Feb 2026 20:39:33 -0700

868. binary gap

Diffstat:
M
binary_gap.c
 | 
29
+++++++++++++++++++----------
M
binary_gap.py
 | 
22
++++++++++++++--------

2 files changed, 33 insertions(+), 18 deletions(-)
diff --git a/binary_gap.c b/binary_gap.c
@@ -10,20 +10,29 @@
  */
 
 int binaryGap(int n) {
-  int ans = 0, prev = -1;
-  for (int i = 0; n > 0; i++) {
+  if (__builtin_popcount(n) == 1)
+    return 0;
+  n >>= __builtin_ctz(n);
+  int max_gap = 0, gap = 0;
+  while (n) {
     if (n & 1) {
-      if (prev != -1)
-        ans = fmax(ans, i - prev);
-      prev = i;
-    }
+      max_gap = fmax(max_gap, gap);
+      gap = 0;
+    } else
+      gap++;
     n >>= 1;
   }
-  return ans;
+  return max_gap + 1;
 }
 
 int main() {
-  printf("%d\n", binaryGap(22)); // expect: 2
-  printf("%d\n", binaryGap(8));  // expect: 0
-  printf("%d\n", binaryGap(5));  // expect: 2
+  int r1 = binaryGap(22);
+  int r2 = binaryGap(8);
+  int r3 = binaryGap(5);
+  printf("%d\n", r1); // expect: 2
+  assert(r1 == 2);
+  printf("%d\n", r2); // expect: 0
+  assert(r2 == 0);
+  printf("%d\n", r3); // expect: 2
+  assert(r3 == 2);
 }
diff --git a/binary_gap.py b/binary_gap.py
@@ -9,14 +9,20 @@ bit positions.
 """
 
 
-class Solution(object):
-    def binaryGap(self, n):
-        """
-        :type n: int
-        :rtype: int
-        """
-        idx = [i for i, j in enumerate(bin(n)) if j == "1"]
-        return max([j - i for i, j in zip(idx, idx[1:])] or [0])
+class Solution:
+    def binaryGap(self, n: int) -> int:
+        if (n & (n - 1)) == 0:
+            return 0
+        n //= n & -n
+        max_gap, gap = 0, 0
+        while n:
+            if n & 1:
+                max_gap = max(max_gap, gap)
+                gap = 0
+            else:
+                gap += 1
+            n >>= 1
+        return max_gap + 1
 
 
 if __name__ == "__main__":