Given two binary strings such as "1010" and "1011", return their sum as a binary string, here "10101" (LeetCode 67).
Walk both strings from the right with two indices and a carry. At each step add the available digits and the carry; the output bit is total % 2 and the new carry is total // 2. Keep going while either index is valid or the carry is non-zero, which handles unequal lengths and the final overflow bit in one condition.
def add_binary(a, b):
i, j, carry = len(a) - 1, len(b) - 1, 0
out = []
while i >= 0 or j >= 0 or carry:
total = carry
if i >= 0:
total += ord(a[i]) - 48; i -= 1
if j >= 0:
total += ord(b[j]) - 48; j -= 1
out.append(str(total % 2))
carry = total // 2
return "".join(reversed(out))
Append and reverse once at the end. Prepending to a string inside the loop is O(n^2) in most languages.
In Python, bin(int(a, 2) + int(b, 2))[2:] works, and Python handles big ints. Mention it, but expect the interviewer to ask for the manual version: in Java or C++ the inputs can be up to 10^4 bits and overflow any built-in type.
Replace 2 with any base and the same loop solves Add Strings (base 10) and Add Two Numbers on linked lists. Saying that shows you see the pattern rather than memorizing one problem.
O(max(m, n)) time and space for the output.
Disclosure: I work on Linkjob AI. If you want structured practice for interviews like this, linkjob.ai can help you rehearse and get real-time hints.