LC67. Add Binary

Approach 1: Iteration

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        n = max(len(a), len(b))
        a, b = a.zfill(n), b.zfill(n)
 
        res = [''] * (n + 1)
 
        carry = 0
        for i in range(n - 1, -1, -1):
            res[i] = str((carry + int(a[i]) + int(b[i])) % 2)
            carry = (carry + int(a[i]) + int(b[i])) // 2
        
        if carry == 1:
            res = ['1'] + res 
 
        return ''.join(res)

Complexity

Time: $O(max(a,b))$
Space: $O(max(a,b))$

Approach 2: Bit-twiddling

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        a, b = int(a, 2), int(b, 2)
 
        while b > 0:
            a, b = a ^ b, (a & b) << 1
        
        return bin(a)[2:]

Notes

TODO

Other Languages