Apparently you can bit manipulation to perform binary addition. This is the Python code for it:
class Solution:
def addBinary(self, a, b) -> str:
x, y = int(a, 2), int(b, 2)
while y:
answer = x ^ y
carry = (x & y) << 1
x, y = answer, carry
return bin(x)[2:]
Basically what is being done is converting the binary strings to integers in base 10 form. Then doing XOR between the two numbers. The XOR is the sum disregarding the carry. Then the carry is calculated separately by ANDing x and y. In the next iteration round the sum of the carry and the previous sum are found, and the carry of this is found the same way, until there is no carry left.
I'm having difficulty explaining what the runtime of the while loop would be. Apparently it's O(max(N,M)) where N represents the number of bits in a, and M is the number of bits in b.
But why? Lost on how to analyze the runtime here.
It's not O(max(N,M)) but O(max(N,M)^2).
Consider a = '1' * N and b = '1'. You'll loop N times, and each time you'll produce an N-bit number. So that's not linear but quadratic.
None of the numbers are longer than max(N,M)+1 bits, and every operation is linear in the number of bits. And after i iterations, the low i bits of y are zeros, so you loop at most O(max(N,M)) times. Hence O(max(N,M)^2) overall.
You can also see the quadratic time experimentally, here are runtimes (in seconds) for N from 100000 to 400000:
100000 0.36107301712036133
200000 1.4743156433105469
400000 5.770820140838623
You can see that doubling N roughly quadruples the time, as quadratic complexity does. The test script:
from time import time
class Solution:
def addBinary(self, a, b) -> str:
x, y = int(a, 2), int(b, 2)
while y:
answer = x ^ y
carry = (x & y) << 1
x, y = answer, carry
return bin(x)[2:]
for N in 100_000, 200_000, 400_000:
a = '1' * N
b = '1'
t = time()
Solution().addBinary(a, b)
print(N, time() - t)