Add Binary

LeetCode 67: Add Binary Solution & Explanation

Problem Overview

TL;DR: The optimal solution simulates bitwise addition from right to left using two pointers and a carry variable, treating the strings as arrays of digits.

The Add Binary problem asks us to take two non-empty binary strings, a and b, and return their summation as a binary string. Instead of interpreting these strings as standard integers—which could easily overflow standard data types given the constraints—we must perform the addition logically, character by character.

This is a classic "LeetCode 67" problem often used in interviews to test a candidate's ability to handle string manipulation and elementary arithmetic logic without relying on built-in big integer libraries.

Brute Force Approach for Add Binary

The most intuitive approach for a beginner might be to convert the binary strings into integer types, perform the addition, and then convert the result back into a binary string.

Naive Algorithm

1. Parse string a into an integer (base 2).
2. Parse string b into an integer (base 2).
3. Compute sum = int_a + int_b.
4. Convert sum back to a binary string representation.

Pseudo-code

function addBinary(a, b):
    num1 = parseBinary(a)
    num2 = parseBinary(b)
    total = num1 + num2
    return toBinaryString(total)

Why this Fails

While this approach is logically sound for small inputs, it fails due to Integer Overflow in strictly typed languages like C++ or Java.

The problem constraints state that the length of the strings can be up to $10^4$. A standard 64-bit integer (long long in C++ or long in Java) can only store values up to $2^{63}-1$. A binary string of length $10^4$ represents a number roughly equal to $2^{10000}$, which is exponentially larger than what standard CPU registers can hold.

Although Python handles arbitrarily large integers automatically, relying on this feature defeats the purpose of the algorithmic interview question, which is to implement the addition logic manually.

Algorithm Strategy: Array - Plus One (Handling Carry)

The strategy strictly follows the "Handling Carry" subpattern:

1. Initialization: Create two pointers, i and j, pointing to the last characters of strings a and b respectively. Initialize an integer carry to 0. Use a mutable string builder (or dynamic array) to construct the result.
2. Iteration: Loop as long as either pointer is valid (non-negative) OR carry is non-zero. This ensures we process all digits and don't drop a final carry (e.g., $1 + 1 = 10$).
3. Digit Extraction: inside the loop, extract the numeric value of the current characters. If a pointer has moved past the beginning of the string (index < 0), treat the value as 0.
4. Computation:
   • Calculate sum = digit_a + digit_b + carry.
   • Determine the current result bit: sum % 2.
   • Determine the new carry: sum / 2 (integer division).
5. Construction: Append the result bit to our builder.
6. Finalization: Since we appended bits from least significant to most significant (right to left), the result string is currently backwards. Reverse the string to obtain the final correct binary representation.

Execution Flow

Let's trace a = "11", b = "1".

1. Start: i = 1 (points to last '1' in "11"), j = 0 (points to '1'), carry = 0.
2. Iteration 1:
   • val_a = 1, val_b = 1.
   • total = 1 + 1 + 0 = 2.
   • bit = 2 % 2 = 0. Append "0".
   • carry = 2 / 2 = 1.
   • Decrement i to 0, j to -1.
3. Iteration 2:
   • val_a = 1 (at index 0), val_b = 0 (index out of bounds).
   • total = 1 + 0 + 1 (carry) = 2.
   • bit = 2 % 2 = 0. Append "0". Result is now "00".
   • carry = 2 / 2 = 1.
   • Decrement i to -1, j to -2.
4. Iteration 3:
   • Pointers are invalid, but loop continues because carry (1) > 0.
   • val_a = 0, val_b = 0.
   • total = 0 + 0 + 1 = 1.
   • bit = 1 % 2 = 1. Append "1". Result is now "001".
   • carry = 1 / 2 = 0.
5. End: Loop terminates.
6. Reverse: "001" becomes "100".

Proof of Correctness

The correctness of this algorithm relies on the mathematical properties of addition in positional numeral systems.

1. Invariant: At any step $k$ (processing the $k$-th bit from the right), the computed bit is strictly $(A_k + B_k + C_{k-1}) \pmod 2$, and the carry passed to step $k+1$ is $\lfloor (A_k + B_k + C_{k-1}) / 2 \rfloor$. This matches the definition of binary addition.
2. Termination: The loop processes every bit of the longer string exactly once. The condition carry > 0 ensures that if the most significant bits sum to a value $\ge 2$, the resulting overflow creates a new most significant bit (MSB), preventing data loss.
3. Boundary Handling: By treating out-of-bounds indices as 0, we effectively pad the shorter string with leading zeros without allocating extra memory, preserving the numeric value.

Pattern Reuse Notes

The Array - Plus One (Handling Carry) pattern is fundamental for arbitrary-precision arithmetic. You can apply this exact logic to:

• LeetCode 66: Plus One: Similar logic, but you are only adding 1 to a single array of digits representing a number.
• LeetCode 43: Multiply Strings: Multiplication is essentially repeated addition with shifts; managing the carry is the central component of the inner loop.
• LeetCode 989: Add to Array-Form of Integer: Identical to Add Binary, but in base-10 using an array and an integer.

Reference Implementation

C++ Solution for LeetCode 67

1class Solution {
2public:
3    string addBinary(string a, string b) {
4        string result = "";
5        int i = a.length() - 1;
6        int j = b.length() - 1;
7        int carry = 0;
8
9        // Iterate as long as we have digits or a remaining carry
10        while (i >= 0 || j >= 0 || carry > 0) {
11            int sum = carry;
12            
13            // Add digit from a if available
14            if (i >= 0) {
15                sum += a[i] - '0'; // Convert char to int
16                i--;
17            }
18            
19            // Add digit from b if available
20            if (j >= 0) {
21                sum += b[j] - '0'; // Convert char to int
22                j--;
23            }
24            
25            // sum % 2 is the current digit, sum / 2 is the carry
26            result += to_string(sum % 2);
27            carry = sum / 2;
28        }
29
30        // The result was built backwards, so reverse it
31        reverse(result.begin(), result.end());
32        return result;
33    }
34};

Java Solution for LeetCode 67

1class Solution {
2    public String addBinary(String a, String b) {
3        StringBuilder sb = new StringBuilder();
4        int i = a.length() - 1;
5        int j = b.length() - 1;
6        int carry = 0;
7
8        // Iterate backwards through both strings
9        while (i >= 0 || j >= 0 || carry > 0) {
10            int sum = carry;
11            
12            if (i >= 0) {
13                sum += a.charAt(i) - '0'; // Convert char to int
14                i--;
15            }
16            if (j >= 0) {
17                sum += b.charAt(j) - '0'; // Convert char to int
18                j--;
19            }
20            
21            // Append current bit (remainder)
22            sb.append(sum % 2);
23            // Update carry (quotient)
24            carry = sum / 2;
25        }
26
27        // Reverse to get the correct order
28        return sb.reverse().toString();
29    }
30}

Python Solution for LeetCode 67

1class Solution:
2    def addBinary(self, a: str, b: str) -> str:
3        res = []
4        i, j = len(a) - 1, len(b) - 1
5        carry = 0
6        
7        # Process both strings from right to left
8        while i >= 0 or j >= 0 or carry:
9            total = carry
10            
11            if i >= 0:
12                total += int(a[i])
13                i -= 1
14            if j >= 0:
15                total += int(b[j])
16                j -= 1
17            
18            # Append the least significant bit of total
19            res.append(str(total % 2))
20            # Update carry
21            carry = total // 2
22            
23        # Reverse the list and join to form the string
24        return "".join(res[::-1])