## # Solution

### # Convert to Int (Cheating)

Use the built-in functions int to convert and format/f-strings to return a string.

Using format function:

def addBinary(self, a: str, b: str) -> str:
return '{0:b}'.format(int(a, 2) + int(b, 2))


Using f-strings:

def addBinary(self, a: str, b: str) -> str:
return f'{int(a,2)+int(b,2):b}'


### # DIY RCA

We could DIY an RCA (ripple carry adder).

Complexity:

• Time: $O(\max(N,M))$
• Space: $O(\max(N,M))$
def addBinary(self, a: str, b: str) -> str:
n = max(len(a), len(b))
a, b = a.zfill(n), b.zfill(n)

carry = 0
for i in reversed(range(n)):
if a[i] == '1':
carry += 1
if b[i] == '1':
carry += 1

if carry % 2 == 1:
else:

carry //= 2

if carry == 1:



### # Bit Manipulation

This solution requires previous knowledge, or supreme ingenuity (See in more detail at Leetcode solution).

Use x to store the sum (XOR of 2 binaries) and y to store the carry (AND of 2 binaries and left shifted by 1). Keep doing this until carry is 0.

Complexity:

• Time: $O(\max(N,M))$
• Space: $O(\max(N,M))$
def addBinary(self, a: str, b: str) -> str:
x, y = int(a, 2), int(b, 2)
while y:
carry = (x & y) << 1

def addBinary(self, a: str, b: str) -> str: