leetcode

commit f6409fced6cbd96171cfd8fab742d75388cce0b5
parent da7d5339764626a55f99e426551e2ecdd034a169
Author: Jack Sangdahl <jack@pngu.org>
Date:   Fri, 14 Nov 2025 08:19:30 -0700

868. binary gap

Diffstat:
A
binary_gap.c
 | 
29
+++++++++++++++++++++++++++++
A
binary_gap.py
 | 
26
++++++++++++++++++++++++++

2 files changed, 55 insertions(+), 0 deletions(-)
diff --git a/binary_gap.c b/binary_gap.c
@@ -0,0 +1,29 @@
+// 868. Binary Gap
+#include "leetcode.h"
+
+/*
+ * given a positive integer 'n', find and return the longest distance between
+ * any two adjacent 1's in the binary representation of 'n'. if there are no two
+ * adjacent 1's, return 0. two 1's are adjacent if there are only 0's separating
+ * them. the distance between two 1's is the absolute difference between their
+ * bit positions.
+ */
+
+int binaryGap(int n) {
+  int ans = 0, prev = -1;
+  for (int i = 0; n > 0; i++) {
+    if (n & 1) {
+      if (prev != -1)
+        ans = fmax(ans, i - prev);
+      prev = i;
+    }
+    n >>= 1;
+  }
+  return ans;
+}
+
+int main() {
+  printf("%d\n", binaryGap(22)); // expect: 2
+  printf("%d\n", binaryGap(8));  // expect: 0
+  printf("%d\n", binaryGap(5));  // expect: 2
+}
diff --git a/binary_gap.py b/binary_gap.py
@@ -0,0 +1,26 @@
+# 868. Binary Gap
+
+"""
+given a positive integer 'n', find and return the longest distance between
+any two adjacent 1's in the binary representation of 'n'. if there are no two
+adjacent 1's, return 0. two 1's are adjacent if there are only 0's separating
+them. the distance between two 1's is the absolute difference between their
+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])
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.binaryGap(n=22))
+    print(obj.binaryGap(n=8))
+    print(obj.binaryGap(n=5))