Add Binary

Add Binary

What is this problem about?

The Add Binary interview question asks you to take two strings representing binary numbers (strings of '0's and '1's) and return their sum as a new binary string. While it sounds like simple addition, the catch is that the input strings can be extremely long, far exceeding the capacity of standard 64-bit integer types in languages like Java or C++.

Why is this asked in interviews?

Companies like Meta, Amazon, and Microsoft use this Add Binary coding problem to assess a candidate's comfort with manual simulation and string manipulation. It tests your ability to handle carries and iterate through sequences of different lengths without relying on built-in "shortcut" functions that convert strings to integers.

Algorithmic pattern used

This problem follows the Math and Simulation interview pattern. Specifically, it uses the Schoolbook Addition method. You iterate from the end of both strings (the least significant bit) toward the beginning, maintaining a "carry" variable that is passed to the next position.

Example explanation

Suppose we want to add $a = "1011"$ and $b = "110"$.

1. Rightmost bits: $1 + 0 = 1$. Carry is 0.
2. Next bits: $1 + 1 = 2$. In binary, this is "10". So, write $0$, carry $1$.
3. Next bits: $0 + 1 + carry(1) = 2$. Write $0$, carry $1$.
4. Leftmost bits: $1 + 0 (empty) + carry(1) = 2$. Write $0$, carry $1$.
5. Final carry: Append the leftover $1$. Result: "10001".

Common mistakes candidates make

• Integer Overflow: Attempting to convert the strings to integers, adding them, and then converting back to binary. This fails for very long strings.
• Wrong String Order: Forgetting that string indices go from left to right, while math addition goes from right to left.
• Handling the Final Carry: Many candidates finish the loop but forget to check if a carry remains that requires an extra '1' at the start of the string.

Interview preparation tip

When working with strings in a simulation like this, use a StringBuilder or a character array. Appending to a string in a loop in languages like Java or Python creates many intermediate objects, leading to $O(N^2)$ time complexity instead of the optimal $O(N)$.