Add Binary - Solution & Explanation

Problem Overview: You are given two binary strings a and b. Add them together and return the result as a binary string. The challenge is handling binary addition rules (0+0, 0+1, 1+1) and propagating the carry correctly across digits.

Approach 1: Bit-by-Bit Addition with Carry (Time: O(n), Space: O(n))

This approach simulates the same process you use when adding numbers by hand. Start from the rightmost digits of both strings and move left. At each step, convert the current characters to integers, add them with a carry, compute the resulting bit using sum % 2, and update the carry using sum // 2. Append the computed bit to a result builder and continue until both strings and the carry are exhausted. Since you scan each digit once, the time complexity is O(n) where n is the length of the longer string, and space complexity is O(n) for the output string. This method directly uses concepts from math and bit manipulation while treating the process as a simple string traversal.

Approach 2: Using Built-in Big Integer Libraries (Time: O(n), Space: O(n))

Some languages provide built-in support for large integers that can parse binary strings directly. Convert both binary strings into integers using base-2 parsing, perform a normal integer addition, and convert the result back to a binary string. For example, Python's int(a, 2) or Java's BigInteger can handle arbitrarily large values. The time complexity remains O(n) due to parsing and conversion, and space complexity is O(n) for the resulting binary representation. This approach is concise and readable but relies on language features rather than demonstrating algorithmic understanding.

Recommended for interviews: The bit-by-bit addition approach is the one interviewers expect. It shows you understand binary arithmetic, carry propagation, and efficient string traversal. The big integer approach works in production code when readability matters, but it hides the underlying logic that interviewers typically want to evaluate.