Add Binary

How it works

Instead of reversing the strings upfront, we can use two pointers starting at the end of each string and work backward. This avoids the extra space and time needed to reverse the input strings. We continue until both pointers have moved past the beginning of their strings and no carry remains. The result is built in reverse order, so we reverse it once at the end.

Steps

1. Initialize pointers i and j at the last index of strings a and b.
2. Initialize carry = 0 and an empty result list.
3. While i >= 0 or j >= 0 or carry > 0:
   • Get the digit at position i in a (0 if i < 0).
   • Get the digit at position j in b (0 if j < 0).
   • Calculate total = digitA + digitB + carry.
   • Append total % 2 to the result.
   • Update carry = total / 2.
   • Decrement both i and j.
4. Reverse the result and return as a string.

Complexity

• Time complexity: O(max(m, n))
• Space complexity: O(max(m, n))

Where m and n are the lengths of the strings a and b respectively.

Things to watch for

Forgetting the Final Carry

After processing all digits, there may still be a carry of 1 that needs to be added to the result. Forgetting to check for this will produce incorrect results for cases like "1" + "1" = "10".

Processing Strings in Wrong Direction

Binary addition must process digits from right to left (least significant to most significant). A common mistake is iterating from the start of the strings instead of the end, which produces completely wrong results.

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        res = []
        carry = 0

        i, j = len(a) - 1, len(b) - 1
        while i >= 0 or j >= 0 or carry > 0:
            digitA = int(a[i]) if i >= 0 else 0
            digitB = int(b[j]) if j >= 0 else 0

            total = digitA + digitB + carry
            res.append(total % 2)
            carry = total // 2

            i -= 1
            j -= 1

        res.reverse()
        return ''.join(map(str, res))

class Solution {
public:
    string addBinary(string a, string b) {
        string res = "";
        int carry = 0;

        int i = a.size() - 1, j = b.size() - 1;
        while (i >= 0 || j >= 0 || carry > 0) {
            int digitA = i >= 0 ? a[i] - '0' : 0;
            int digitB = j >= 0 ? b[j] - '0' : 0;

            int total = digitA + digitB + carry;
            res += (total % 2) + '0';
            carry = total / 2;

            i--;
            j--;
        }

        reverse(res.begin(), res.end());
        return res;
    }
};