Add Binary - Solution & Explanation

Problem Overview: You are given two binary strings a and b. Add them and return the result as another binary string. The challenge is performing binary addition manually since the inputs can be longer than typical integer limits.

Approach 1: Bit-by-Bit Addition with Carry (O(n) time, O(n) space)

This approach simulates how binary addition works on paper. Start from the rightmost digit of both strings and move left. At each step, add the current bits along with a carry. The sum determines the resulting bit (sum % 2) and the new carry (sum // 2). Continue until both strings are processed. If a carry remains at the end, append it to the result.

Use two pointers starting from the end of each string. If one string is shorter, treat missing digits as 0. Store resulting bits in a list or string builder and reverse at the end. This approach directly mirrors binary arithmetic and avoids integer overflow issues. Time complexity is O(n) where n is the length of the longer string. Space complexity is O(n) for the result string.

This solution relies on concepts from string traversal and bit manipulation. Many interviewers expect this approach because it demonstrates understanding of binary arithmetic rather than relying on built-in conversions.

Approach 2: Using Built-in Big Integer Libraries (O(n) time, O(n) space)

Another option converts the binary strings to integers using built-in language features, performs normal addition, and converts the result back to binary. In Python, use int(a, 2) and bin(sum). In JavaScript, BigInt can handle arbitrarily large numbers. Java provides BigInteger for the same purpose.

This approach is concise and easy to implement, but it relies on language-level big integer support. Internally, these libraries still perform bit operations with complexity proportional to the number of digits, giving roughly O(n) time and O(n) space. The tradeoff is less control over the algorithm and reduced demonstration of algorithmic reasoning.

The technique relates to math operations on different number bases. It works well in production code when readability matters more than demonstrating low-level logic.

Recommended for interviews: Bit-by-bit addition with carry is the expected solution. It shows that you understand binary arithmetic and can simulate operations using simple iteration and state management. The big integer approach is acceptable in real-world code but usually not the answer interviewers want first.