LeetCode Problem 67

Difficulty: 🟢 Easy
Topics: Math, String, Bit Manipulation, Simulation

Solution

LeetCode 67, Add Binary

Problem Statement

You are given two strings, a and b, where each string represents a binary number. A binary number contains only the characters '0' and '1'. The task is to add these two binary numbers together and return the result as another binary string.

Unlike normal decimal addition, binary addition follows base 2 rules. Each digit can only be 0 or 1, and when the sum of two digits exceeds 1, a carry is produced for the next position.

For example:

• 1 + 1 = 10 in binary, which means the current digit becomes 0 and the carry becomes 1
• 1 + 1 + 1 = 11, which means the current digit becomes 1 and the carry remains 1

The input strings can be as long as 10^4 characters, which means the solution must efficiently process large binary numbers. Since the strings may exceed the size of standard integer types in many programming languages, directly converting them into integers is not always safe or portable. Instead, the intended solution is to simulate binary addition manually, just like elementary school addition from right to left.

The problem guarantees that:

• Both strings contain only '0' and '1'
• Neither string contains leading zeros unless the value itself is "0"
• Both strings have length at least 1

Several edge cases are important to consider:

• One string may be significantly longer than the other
• The addition may produce an extra carry at the end, such as "1" + "1" = "10"
• Both strings may contain only zeros
• Very large inputs require an efficient linear-time solution

Approaches

Brute Force Approach

A straightforward idea is to convert both binary strings into integers, add them, and then convert the result back into a binary string.

In Python, this can be done using built-in functions such as int(a, 2) and bin(sum)[2:]. While this approach is concise, it relies heavily on language support for arbitrarily large integers.

In some languages, especially those with fixed-width integer types, very large binary strings can overflow standard integer storage. Since the input length can reach 10^4, the binary value may be far larger than 64-bit integer limits.

Even though Python can technically handle arbitrarily large integers, this approach avoids the intended binary addition logic and is not universally portable across languages.

Optimal Approach

The better solution is to simulate binary addition manually.

The key observation is that binary addition behaves exactly like decimal addition, except each digit is either 0 or 1. We process the strings from right to left because the least significant bits are located at the end of the strings.

At each position:

1. Add the current bits from both strings
2. Add the carry from the previous step
3. Compute the resulting bit using modulo 2
4. Compute the new carry using integer division by 2

This approach works efficiently in linear time and avoids any overflow concerns.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Converts binary strings into integers and back
Optimal	O(n)	O(n)	Simulates binary addition directly from right to left

Algorithm Walkthrough

1. Initialize two pointers, one at the end of string a and one at the end of string b. These pointers represent the current binary digits being processed.
2. Initialize a variable called carry with value 0. This stores overflow from the previous addition step.
3. Create an empty list to store the resulting binary digits. A list is used because appending characters is efficient, while repeated string concatenation is expensive.
4. Continue processing while:

• there are still digits left in a, or
• there are still digits left in b, or
• there is still a remaining carry

5. For each iteration:

• Start with the current carry
• If the pointer in a is valid, add the numeric value of that bit
• If the pointer in b is valid, add the numeric value of that bit

6. Compute the resulting binary digit:

• total % 2 gives the current bit
• total // 2 gives the new carry

7. Append the resulting bit to the result list.
8. Move both pointers one step to the left.
9. After processing all digits, reverse the result list because digits were collected from least significant to most significant.
10. Join the characters into a final string and return it.

Why it works

At every step, the algorithm correctly computes the sum of the corresponding binary digits and the incoming carry. The carry propagation follows the exact rules of binary arithmetic. Since every digit position is processed exactly once, and the carry is always preserved correctly, the final result is guaranteed to be the correct binary sum.

Python Solution

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        pointer_a = len(a) - 1
        pointer_b = len(b) - 1

        carry = 0
        result = []

        while pointer_a >= 0 or pointer_b >= 0 or carry:
            total = carry

            if pointer_a >= 0:
                total += int(a[pointer_a])
                pointer_a -= 1

            if pointer_b >= 0:
                total += int(b[pointer_b])
                pointer_b -= 1

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

        return "".join(reversed(result))

The implementation closely follows the algorithm described earlier.

Two pointers start from the ends of the strings because binary addition proceeds from the least significant digit to the most significant digit. The carry variable stores overflow between iterations.

During each loop iteration, the algorithm computes the total sum for the current position by combining:

• the current bit from a
• the current bit from b
• the previous carry

The resulting binary digit is determined using total % 2, while the new carry is computed using total // 2.

The digits are appended to the result list in reverse order because processing starts from the rightmost side of the strings. At the end, the list is reversed and joined into the final binary string.

Go Solution

func addBinary(a string, b string) string {
    pointerA := len(a) - 1
    pointerB := len(b) - 1

    carry := 0
    result := make([]byte, 0)

    for pointerA >= 0 || pointerB >= 0 || carry > 0 {
        total := carry

        if pointerA >= 0 {
            total += int(a[pointerA] - '0')
            pointerA--
        }

        if pointerB >= 0 {
            total += int(b[pointerB] - '0')
            pointerB--
        }

        result = append(result, byte(total%2)+'0')
        carry = total / 2
    }

    left := 0
    right := len(result) - 1

    for left < right {
        result[left], result[right] = result[right], result[left]
        left++
        right--
    }

    return string(result)
}

The Go implementation follows the same logic as the Python version, but there are a few language-specific details.

Go strings are immutable, so a []byte slice is used to build the result efficiently. Characters are converted into integer digits using subtraction with '0'.

Since digits are appended in reverse order, the byte slice must be reversed manually before converting it back into a string.

There are no integer overflow concerns because the algorithm only ever stores small values between 0 and 3 during each addition step.

Worked Examples

Example 1

Input:

a = "11"
b = "1"

Step-by-step execution:

Iteration	pointer_a	pointer_b	carry	total	result
Start	1	0	0	-	[]
1	1	0	0	2	["0"]
2	0	-1	1	2	["0", "0"]
3	-1	-1	1	1	["0", "0", "1"]

The result list is currently reversed:

["0", "0", "1"]

After reversing:

"100"

Example 2

Input:

a = "1010"
b = "1011"

Step-by-step execution:

Iteration	a bit	b bit	carry in	total	output bit	carry out	result
1	0	1	0	1	1	0	["1"]
2	1	1	0	2	0	1	["1", "0"]
3	0	0	1	1	1	0	["1", "0", "1"]
4	1	1	0	2	0	1	["1", "0", "1", "0"]
5	-	-	1	1	1	0	["1", "0", "1", "0", "1"]

Reversing the result:

"10101"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each digit is processed exactly once
Space	O(n)	The result string stores up to n + 1 digits

Here, n represents the length of the longer input string.

The algorithm performs a single pass from right to left across both strings. Every iteration processes one binary digit and performs constant-time operations. The result storage requires linear space because the output itself may contain up to one additional digit beyond the larger input length.

Test Cases

solution = Solution()

assert solution.addBinary("11", "1") == "100"  # basic carry generation
assert solution.addBinary("1010", "1011") == "10101"  # multiple carries
assert solution.addBinary("0", "0") == "0"  # both inputs zero
assert solution.addBinary("1", "0") == "1"  # one zero input
assert solution.addBinary("1", "1") == "10"  # single carry
assert solution.addBinary("1111", "1") == "10000"  # carry propagates through all bits
assert solution.addBinary("100", "110010") == "110110"  # different length strings
assert solution.addBinary("1010101010", "0101010101") == "1111111111"  # alternating bits
assert solution.addBinary("1111111111111111", "1") == "10000000000000000"  # large carry chain
assert solution.addBinary("0", "111") == "111"  # leading zero value case

Test	Why
"11" + "1"	Validates basic carry handling
"1010" + "1011"	Validates multiple carry operations
"0" + "0"	Tests smallest zero inputs
"1" + "0"	Tests addition with one zero
"1" + "1"	Tests single-bit overflow
"1111" + "1"	Tests cascading carry propagation
"100" + "110010"	Tests unequal string lengths
Alternating bit patterns	Tests mixed additions without repeated carries
Large carry chain	Tests continuous carry propagation
"0" + "111"	Tests preservation of non-zero input

Edge Cases

Final Carry After Processing All Digits

One of the most common sources of bugs is forgetting to process the final carry after both strings have been fully traversed.

For example:

a = "1"
b = "1"

The sum produces "10", which requires an extra digit beyond the original lengths. The implementation handles this correctly because the loop continues while carry is non-zero.

Strings of Different Lengths

Another important edge case occurs when the strings have different lengths.

For example:

a = "101"
b = "1"

Once the shorter string is exhausted, the algorithm must continue processing the remaining digits of the longer string. The implementation checks each pointer independently, so it safely handles uneven lengths.

Long Carry Propagation

Inputs containing many consecutive 1 bits can produce long carry chains.

For example:

a = "111111"
b = "1"

Every position generates another carry. A buggy implementation might stop too early or mishandle repeated carries. This solution correctly propagates the carry through every digit until no carry remains.

Both Inputs Are Zero

The smallest valid input is:

a = "0"
b = "0"

Some implementations accidentally return an empty string if they rely on non-zero carries to produce output. This implementation correctly processes the single digits and returns "0".