Problem Statement in English

You’re given two binary strings a and b, return their sum as a binary string.

Approach

You iterate over the strings and handle sum and carry yourself, although it looks a little messy and isn’t exactly a delight to implement.

A nicer approach while still using bitwise operators is to convert the binary strings to integers, then use the bitwise XOR operator to calculate the sum without carry, and the bitwise AND operator to calculate the carry. You can then shift the carry left by one position and repeat the process until there is no carry left.

Finally, convert the result back to a binary string.

And we’re done!

Solution in Python


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

Complexity

  • Time: $O(n)$
    Since we are iterating through the length of the binary strings a and b, the time complexity is linear with respect to the length of the longer string.

  • Space: $O(1)$
    Since we are using a constant amount of space for variables x and y, the space complexity is constant.

Mistakes I Made

I didn’t come up with the idea doing the XOR in one shot and then dealing with the carry.

And we are done.