leetcode

commit c2bc609ab93ea55966b9b67fd736ab168a013690
parent 902d9459f6cd4e135401feb842fb2318dedd1360
Author: Jack Sangdahl <jack@pngu.org>
Date:   Sat, 14 Feb 2026 20:32:17 -0700

67. add binary

Diffstat:
M
add_binary.c
 | 
49
+++++++++++++++++++++++++++++--------------------
A
add_binary.py
 | 
32
++++++++++++++++++++++++++++++++

2 files changed, 61 insertions(+), 20 deletions(-)
diff --git a/add_binary.c b/add_binary.c
@@ -1,28 +1,37 @@
 // 67. Add Binary
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
+#include "leetcode.h"
+
+/*
+ * given two binary strings 'a' and 'b', return their sum as a binary string.
+ */
 
 char *addBinary(char *a, char *b) {
-  int i = strlen(a), j = strlen(b), carry = 0;
-  int k = i > j ? i : j;
-  char *ans = malloc(k + 2);
-  ans[k + 1] = '\0';
-  while (i || j) {
-    if (i)
-      carry += (a[--i] - '0');
-    if (j)
-      carry += (b[--j] - '0');
-    ans[k--] = (carry & 1) + '0';
-    carry >>= 1;
+  int i = strlen(a), j = strlen(b);
+  int k = fmax(i, j) + 2, carry = 0;
+  char *ans = (char *)malloc(k * sizeof(char));
+  i--;
+  j--;
+  ans[--k] = '\0';
+  while (--k >= 0) {
+    carry += i >= 0 ? a[i--] - '0' : 0;
+    carry += j >= 0 ? b[j--] - '0' : 0;
+    ans[k] = carry % 2 + '0';
+    carry /= 2;
   }
-  ans[0] = carry + '0';
-  return ans + (carry ^ 1);
+  if (ans[0] == '0')
+    memmove(ans, ans + 1, strlen(ans) * sizeof(char));
+  return ans;
 }
 
 int main() {
-  char a1[] = "11", b1[] = "1";
-  char a2[] = "1010", b2[] = "1011";
-  printf("%c\n" * addBinary(a1, b1)); // expect: 100
-  printf("%c\n" * addBinary(a2, b2)); // expect: 100
+  char *a1 = "11", *b1 = "1", *r1 = "100";
+  char *a2 = "1010", *b2 = "1011", *r2 = "10101";
+  char *ab1 = addBinary(a1, b1);
+  char *ab2 = addBinary(a2, b2);
+  printf("%s\n", ab1); // expect: 100
+  assert(!strcmp(ab1, r1));
+  printf("%s\n", ab2); // expect: 10101
+  assert(!strcmp(ab2, r2));
+  free(ab1);
+  free(ab2);
 }
diff --git a/add_binary.py b/add_binary.py
@@ -0,0 +1,32 @@
+# 67. Add Binary
+
+"""
+given two binary strings 'a' and 'b', return their sum as a binary string.
+"""
+
+
+class Solution(object):
+    def addBinary(self, a, b):
+        """
+        :type a: str
+        :type b: str
+        :rtype: str
+        """
+        ans, carry = [], 0
+        i, j = len(a) - 1, len(b) - 1
+        while i >= 0 or j >= 0 or carry:
+            if i >= 0:
+                carry += int(a[i])
+                i -= 1
+            if j >= 0:
+                carry += int(b[j])
+                j -= 1
+            ans.append(str(carry % 2))
+            carry //= 2
+        return "".join(reversed(ans))
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.addBinary(a="11", b="1"))
+    print(obj.addBinary(a="1010", b="1011"))