LeetCode 67: Add Binary

Problem Restatement

We are given two binary strings, a and b.

Each string contains only characters "0" and "1".

We need to return their sum as a binary string.

The official constraints are 1 <= a.length, b.length <= 10^4, both strings contain only binary digits, and neither string has leading zeroes except the string "0" itself.

Input and Output

Function shape:

def addBinary(a: str, b: str) -> str:
    ...

Examples

For:

a = "11"
b = "1"

"11" is binary for 3.

"1" is binary for 1.

Their sum is 4, which is:

"100"

So the answer is:

"100"

For:

a = "1010"
b = "1011"

These represent:

1010 = 10
1011 = 11

Their sum is 21, which is:

"10101"

So the answer is:

"10101"

First Thought: Convert to Integers

In Python, we could write:

return bin(int(a, 2) + int(b, 2))[2:]

This is short and works in Python.

But the problem is meant to test manual binary addition. In many languages, the binary strings may be too long for normal integer types.

So we should add the strings directly.

Key Insight

Binary addition works like decimal addition, but each digit is base 2.

We add from right to left.

At each step, we add:

1. The current bit from a
2. The current bit from b
3. The carry from the previous step

The result bit is:

total % 2

The next carry is:

total // 2

For example:

Algorithm

Use two pointers:

i = len(a) - 1
j = len(b) - 1

Use a carry:

carry = 0

Use a list to collect result bits in reverse order:

ans = []

While there is still work to do:

while i >= 0 or j >= 0 or carry:

1. Start with carry.
2. Add a[i] if i is valid.
3. Add b[j] if j is valid.
4. Append total % 2.
5. Set carry = total // 2.
6. Move both pointers left.

At the end, reverse the collected bits and join them.

Correctness

The algorithm processes bits from least significant to most significant, which is the standard order for addition with carry.

At each position, total is exactly the sum of the two input bits at that position plus the carry from all lower positions. The algorithm writes total % 2, which is the correct binary digit for the current position, and carries total // 2, which is the correct amount to add to the next higher position.

If one string is shorter, the algorithm treats missing bits as 0. This matches normal arithmetic.

The loop continues while either string has remaining bits or there is a carry. Therefore no input bit or final carry is lost.

Since the result bits are generated from right to left, reversing them produces the correct binary sum from most significant to least significant.

Complexity

Here, m = len(a) and n = len(b).

Implementation

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        i = len(a) - 1
        j = len(b) - 1
        carry = 0
        ans = []

        while i >= 0 or j >= 0 or carry:
            total = carry

            if i >= 0:
                total += ord(a[i]) - ord("0")
                i -= 1

            if j >= 0:
                total += ord(b[j]) - ord("0")
                j -= 1

            ans.append(str(total % 2))
            carry = total // 2

        return "".join(reversed(ans))

Code Explanation

Start from the rightmost bit of each string:

i = len(a) - 1
j = len(b) - 1

Initialize the carry:

carry = 0

Store answer bits in reverse order:

ans = []

The loop continues while there are bits left or a carry remains:

while i >= 0 or j >= 0 or carry:

Begin each column addition with the carry:

total = carry

If a still has a bit, add it:

if i >= 0:
    total += ord(a[i]) - ord("0")
    i -= 1

If b still has a bit, add it:

if j >= 0:
    total += ord(b[j]) - ord("0")
    j -= 1

The current binary result bit is:

total % 2

The carry for the next position is:

total // 2

Finally, reverse and join:

return "".join(reversed(ans))

Testing

def run_tests():
    s = Solution()

    assert s.addBinary("11", "1") == "100"
    assert s.addBinary("1010", "1011") == "10101"
    assert s.addBinary("0", "0") == "0"
    assert s.addBinary("1", "0") == "1"
    assert s.addBinary("1111", "1") == "10000"
    assert s.addBinary("101", "11") == "1000"
    assert s.addBinary("100", "110010") == "110110"

    print("all tests passed")

run_tests()