Add Binary

Difficulty: Easy
Topics: Math, String, Bit Manipulation, Simulation
Link: https://leetcode.com/problems/add-binary/

Problem Description

Given two binary strings a and b, return their sum as a binary string.

Example 1:

Input: a = "11", b = "1"
Output: "100"

Example 2:

Input: a = "1010", b = "1011"
Output: "10101"

Constraints:

1 <= a.length, b.length <= 104
a and b consist only of '0' or '1' characters.
Each string does not contain leading zeros except for the zero itself.

Solution

1. Problem Deconstruction (500+ words)

Rewrite the Problem

Technical Version:
Given two finite-length strings a and b over the alphabet {'0', '1'}, interpret each string as the binary representation of a non-negative integer, where the most significant bit is at index 0. Compute the integer sum ( S = \text{int}(a) + \text{int}(b) ), where (\text{int}(x)) maps a binary string to its integer value. Return the canonical binary representation of ( S ) as a string, i.e., a sequence of '0’s and '1’s without leading zeros except for the string "0" representing zero.
Beginner Version:
You have two numbers written in binary (using only digits 0 and 1). Your task is to add them together, exactly like adding decimal numbers on paper, but using binary arithmetic rules:
- 0 + 0 = 0
- 0 + 1 = 1
- 1 + 0 = 1
- 1 + 1 = 0, carry 1
- 1 + 1 + carry (1) = 1, carry 1
  Start from the rightmost digits and move left, keeping track of carries. Write the result as a binary string, and remove any extra zeros at the front (unless the answer is exactly zero, in which case keep a single zero).
Mathematical Version:
Let ( a = (a_{n-1} a_{n-2} \dots a_0)2 ) and ( b = (b{m-1} b_{m-2} \dots b_0)2 ) be two binary numbers, where ( a_i, b_j \in {0,1} ). Define ( n = |a|, m = |b| ). Their sum ( s = a + b ) is computed via the recurrence:
[ s_k = (a_k + b_k + c{k-1}) \mod 2 ] [ c_k = \left\lfloor \frac{a_k + b_k + c_{k-1}}{2} \right\rfloor ] for ( k = 0, 1, \dots, \max(n,m)-1 ), with ( c_{-1} = 0 ), and where we define ( a_k = 0 ) for ( k \ge n ) and ( b_k = 0 ) for ( k \ge m ). The result is the binary string of the sequence ( (c_{\max(n,m)} s_{\max(n,m)-1} \dots s_0) ), trimmed of leading zeros except when the entire sequence is zeros.

Constraint Analysis

1 <= a.length, b.length <= 10^4:
- Limitation: The input strings can be up to 10,000 bits long. This precludes conversion to native integer types in languages with fixed-width integers (e.g., 64-bit integers max at ~(2^{64})), because (2^{10000}) is astronomically larger. Solutions must operate directly on the string representation, implying an algorithm with time complexity at most (O(\max(n,m))) and memory proportional to the output length.
- Hidden edge cases: Extremely long strings stress-test memory usage and indexing. Algorithms that allocate large temporary strings (e.g., padding to equal length) must be careful to avoid quadratic time or excessive memory. The upper bound also suggests that (O(n^2)) brute-force approaches are unacceptable.
a and b consist only of '0' or '1' characters:
- Limitation: No invalid characters are present, so we don’t need validation. This simplifies parsing: each character can be directly mapped to integer 0 or 1 via ord(ch) - ord('0') or equivalent.
- Hidden edge cases: None beyond the guarantee.
Each string does not contain leading zeros except for the zero itself:
- Limitation: Inputs are canonical (no extra leading zeros). This means the first character is '1' for any non-zero number, and "0" is the only representation of zero. This property can simplify some logic (e.g., if both strings start with '1', the result may be longer by at most one bit).
- Hidden edge cases: The output must also adhere to this canonical form. A naive addition might produce leading zeros (e.g., "0" + "0" could become "00"), so post-processing is required. Additionally, when the result is zero, we must return "0", not an empty string.

2. Intuition Scaffolding

Generate 3 Analogies

Real-World Metaphor (Column Addition with Coins):
Imagine you have two piles of coins, but the coins are special: they come in denominations that double each column (1¢, 2¢, 4¢, 8¢, …). Each column can hold at most one coin of that denomination. When you add two piles, you combine coins column by column starting from the smallest denomination. If a column ends up with two coins, they “merge” into one coin of the next higher denomination (since two 1¢ coins become one 2¢ coin), leaving the current column empty. This merging propagates leftward, exactly like binary carry.
Gaming Analogy (RPG Inventory Slots):
In a role-playing game, you have inventory slots for items of power levels 0 or 1. Each slot corresponds to a bit position. When you combine two items of power 1 in the same slot, they upgrade to a single item of power 1 in the next higher slot, while the current slot becomes empty (power 0). This cascading upgrade mirrors carry propagation: you start from the lowest slot and resolve overflows upward.
Math Analogy (Polynomial Addition):
A binary string can be seen as a polynomial with coefficients in ({0,1}) evaluated at (x=2). Adding two binary numbers is equivalent to adding two polynomials coefficient-wise. The carry operation corresponds to reducing coefficients modulo 2 and propagating multiples of 2 to the next higher power. This is exactly how addition works in the ring of polynomials over (\mathbb{Z}_2), but with carries because we are evaluating at (x=2) (a base-2 representation).

Common Pitfalls Section

Overflow from Integer Conversion: Attempting to parse the entire string into an integer (e.g., via int(a, 2) in Python) works in Python due to arbitrary-precision integers but fails in languages like C++ or Java for large inputs. Even in Python, it may be considered cheating in an interview setting.
Adding Left-to-Right: Binary addition is least-significant-bit first. Starting from the left requires knowing future carries, making the algorithm much more complex (though possible with lookahead).
Ignoring Final Carry: After processing all bits, a remaining carry of 1 must be appended as a new most significant bit. Forgetting this yields wrong answers for cases like "11" + "1".
Incorrect Padding for Different Lengths: When strings have different lengths, one must align the least significant bits. Padding the shorter string with zeros on the left (i.e., at the most significant side) is incorrect; padding should be implicit by stopping early in the longer string.
Leading Zeros in Output: Failing to trim leading zeros can result in outputs like "00101" instead of "101". However, trimming all zeros would turn "0" into an empty string, so a special case is needed.
Inefficient String Building: Repeated string concatenation (e.g., result = "0" + result) is (O(k^2)) in many languages due to immutability. Instead, use a list of characters and join at the end.
Carry Confusion: Miscomputing the carry as carry = total // 2 works, but some try carry = 1 if total >= 2 else 0, which is equivalent but may lead to off-by-one errors if total could be 3 (when carry-in is 1 and both bits are 1).

3. Approach Encyclopedia

Approach 1: Elementary Addition (Simulation)

Description: Simulate bit-by-bit addition from LSB to MSB, tracking carry.

Pseudocode:

function addBinary(a, b):
    i = a.length - 1
    j = b.length - 1
    carry = 0
    result = []
    while i >= 0 or j >= 0:
        bitA = a[i] if i >= 0 else 0
        bitB = b[j] if j >= 0 else 0
        total = bitA + bitB + carry
        result.append(total % 2)
        carry = total // 2
        i--; j--
    if carry > 0:
        result.append(1)
    reverse(result)
    # Remove leading zeros (keep at least one)
    while len(result) > 1 and result[0] == 0:
        removeFirst(result)
    return result as string

Complexity Proof:
- Time: Let (n = |a|, m = |b|). The loop runs (\max(n,m)) iterations, each doing (O(1)) work (arithmetic on fixed-size digits). Reversal and leading-zero removal are (O(\max(n,m))) as well. Total time: (O(\max(n,m))).
- Space: The result list holds at most (\max(n,m)+1) digits, each a constant-size object (or character). Thus, space is (O(\max(n,m))).

Visualization (Example: a="1010", b="1011"):

Step | i | j | bitA | bitB | carry | total | current | result (LSB first)
-------------------------------------------------------------------------
0    | 3 | 3 |  0   |  1   |   0   |   1   |    1    | [1]
1    | 2 | 2 |  1   |  1   |   0   |   2   |    0    | [1,0]
2    | 1 | 1 |  0   |  0   |   1   |   1   |    1    | [1,0,1]
3    | 0 | 0 |  1   |  1   |   0   |   2   |    0    | [1,0,1,0]
Post-loop: carry=1 → append 1 → [1,0,1,0,1]
Reverse → [1,0,1,0,1] (same here, palindrome)
Trim leading zeros → "10101"

Approach 2: Built-in Arbitrary Precision (Pythonic Shortcut)

Description: Leverage Python’s arbitrary-precision integers to convert, add, and convert back.

Pseudocode:

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

Complexity Proof:
- Time: Conversion int(a,2) takes (O(n)) to parse the string and build the integer. Addition of two big integers takes (O(\max(n,m))) in the number of bits. Conversion to binary via bin is (O(\log S)) but (S) is the sum value, whose bit length is (O(\max(n,m))). So overall (O(\max(n,m))).
- Space: The integers and resulting string use (O(\max(n,m))) memory.
Visualization: Not needed—direct mapping.

Approach 3: Bitwise Simulation (If Integers Allowed)

Description: Use bitwise XOR for sum without carry, AND for carry, and iterate until carry is zero.

Pseudocode:

def addBinary(a, b):
    x, y = int(a,2), int(b,2)
    while y:
        sum_no_carry = x ^ y
        carry = (x & y) << 1
        x, y = sum_no_carry, carry
    return bin(x)[2:]

Complexity Proof:
- Time: Each iteration reduces the number of 1 bits in the carry. In worst case, (O(\text{bit length}) = O(\max(n,m))).
- Space: (O(1)) aside from the integer representations.
Visualization: Not typically used for string inputs.

Approach 4: Parallel Addition with Lookup Table

Description: Precompute results for all pairs of bits and carry-in (8 possibilities) and process chunks for potential speedup. Overkill for this problem.

Optimal Approach Selection:
For interview settings, Elementary Addition is ideal—it demonstrates understanding of base-2 addition, handles constraints, and is language-agnostic.

4. Code Deep Dive

Optimal Solution (Elementary Addition) in Python

def addBinary(a: str, b: str) -> str:
    # Initialize pointers to the last character (least significant bit)
    i = len(a) - 1
    j = len(b) - 1
    carry = 0
    result = []  # Will store characters in reverse order (LSB first)
    
    # Traverse both strings from right to left
    while i >= 0 or j >= 0:
        # Get current bits as integers, default to 0 if index out of range
        bit_a = int(a[i]) if i >= 0 else 0
        bit_b = int(b[j]) if j >= 0 else 0
        
        # Compute sum of bits and incoming carry
        total = bit_a + bit_b + carry
        
        # Current bit is the parity of the sum
        current_bit = total % 2
        # Carry is 1 if sum >= 2, else 0
        carry = total // 2
        
        # Append the current bit (as a string) to the result list
        result.append(str(current_bit))
        
        # Move pointers leftwards
        i -= 1
        j -= 1
    
    # If there is a carry left after processing all bits, append it
    if carry:
        result.append('1')
    
    # The result list currently has the least significant bit at index 0.
    # Reverse it to get the correct order (most significant bit first).
    result.reverse()
    
    # Remove any leading zeros, but keep at least one character.
    # This loop ensures we don't strip all zeros (e.g., "0" stays "0").
    while len(result) > 1 and result[0] == '0':
        result.pop(0)
    
    # Join the list into a single string and return
    return ''.join(result)

Line-by-Line Annotations

def addBinary(a: str, b: str) -> str: – Function signature with type hints for clarity.
i = len(a) - 1 – Index of the last character of a (least significant bit).
j = len(b) - 1 – Index of the last character of b.
carry = 0 – Initialize carry to zero.
result = [] – Empty list to accumulate result bits (as strings).
while i >= 0 or j >= 0: – Continue until both strings are fully traversed. The condition ensures we process all bits even if one string is longer.
bit_a = int(a[i]) if i >= 0 else 0 – Safely get the integer value of the current bit in a. If index is negative, treat as 0 (implicit padding).
bit_b = int(b[j]) if j >= 0 else 0 – Similarly for b.
total = bit_a + bit_b + carry – Sum of current bits and incoming carry. Can be 0, 1, 2, or 3.
current_bit = total % 2 – The bit to output is the sum modulo 2 (parity).
carry = total // 2 – Integer division yields carry (0 or 1).
result.append(str(current_bit)) – Append the bit as a string to the result list.
i -= 1; j -= 1 – Move pointers leftwards toward more significant bits.
if carry: – After the loop, if a carry remains, it becomes the new most significant bit.
result.append('1') – Append that final carry.
result.reverse() – Reverse the list so that the most significant bit is first.
while len(result) > 1 and result[0] == '0': – Remove leading zeros as long as there is more than one character (to preserve “0”).
result.pop(0) – Remove the first character if it’s ‘0’.
return ''.join(result) – Join the list into a string and return.

Edge Case Handling

Example 1 (a="11", b="1"):
- Step-by-step:
  - i=1, j=0: bit_a=1, bit_b=1, carry=0 → total=2 → current=0, carry=1 → result=[‘0’]
  - i=0, j=-1: bit_a=1, bit_b=0, carry=1 → total=2 → current=0, carry=1 → result=[‘0’,‘0’]
  - i=-1, j=-1: loop ends, carry=1 → result=[‘0’,‘0’,‘1’] → reverse → [‘1’,‘0’,‘0’] → trim → “100”.
Example 2 (a="1010", b="1011"):
- As shown in visualization, yields “10101”.
Zero case (a="0", b="0"):
- i=0, j=0: bit_a=0, bit_b=0, carry=0 → total=0 → current=0, carry=0 → result=[‘0’]
- Loop ends, carry=0 → result=[‘0’] → reverse → [‘0’] → trim (len=1, so no change) → “0”.
Different lengths with carry propagation (a="1111", b="1"):
- i=3, j=0: 1+1+0=2 → current=0, carry=1 → result=[‘0’]
- i=2, j=-1: 1+0+1=2 → current=0, carry=1 → result=[‘0’,‘0’]
- i=1, j=-1: 1+0+1=2 → current=0, carry=1 → result=[‘0’,‘0’,‘0’]
- i=0, j=-1: 1+0+1=2 → current=0, carry=1 → result=[‘0’,‘0’,‘0’,‘0’]
- Loop ends, carry=1 → result=[‘0’,‘0’,‘0’,‘0’,‘1’] → reverse → [‘1’,‘0’,‘0’,‘0’,‘0’] → trim → “10000”.

5. Complexity War Room

Hardware-Aware Analysis

Time: (O(\max(n,m))) with a small constant. For (n,m \leq 10^4), the worst-case iteration count is 10,000. On a modern CPU (≈3 GHz), each iteration may take a few nanoseconds, totaling tens of microseconds—negligible.
Space: The result list holds at most 10,001 characters (if carry propagates). In Python, each character in a list is a pointer (8 bytes) to a string object, and each one-character string object has overhead (~49 bytes). However, since we store strings '0' and '1', Python interns small strings, so the overhead is reduced. Estimated memory: ~(10,001 * 8) bytes for pointers + constant for the two unique string objects ≈ 80 KB, fitting comfortably in L2/L3 cache (typically >256 KB).
Cache Behavior: Sequential access to input strings and result list exhibits good locality, prefetching friendly.

Industry Comparison Table

Approach	Time Complexity	Space Complexity	Readability	Interview Viability
Brute Force (nested loops)	(O(2^{\max(n,m)})) (if enumerating all sums)	(O(1))	2/10	❌ Impossible
Elementary Addition	(O(\max(n,m)))	(O(\max(n,m)))	9/10	✅ Ideal, demonstrates fundamentals
Built-in (Python int)	(O(\max(n,m)))	(O(\max(n,m)))	10/10	⚠️ Acceptable in Python, but may not test algorithm skills
Bitwise (if ints allowed)	(O(\max(n,m)))	(O(1)) extra	7/10	⚠️ Only if integer conversion is allowed
Parallel Chunking	(O(\max(n,m)/k)) with k-word parallelism	(O(1))	5/10	❌ Overly complex

6. Pro Mode Extras

Variants Section

Add Multiple Binary Strings (LeetCode 67 extended):
- Given a list of binary strings, return their sum.
- Solution: Extend elementary addition to process multiple bits per column, with carry that can be larger than 1. Alternatively, iteratively add two strings using the above function. Complexity: (O(L \cdot k)) if done sequentially, where (L) is total length and (k) number of strings.
Add Two Numbers Represented as Linked Lists (LeetCode 2, 445):
- Digits stored in reverse/normal order in singly-linked lists.
- Solution: For reverse order (LeetCode 2), simulate addition while traversing both lists, creating a new list. For normal order (LeetCode 445), use stacks or reverse the lists first.
Add Strings (Decimal) (LeetCode 415):
- Same problem but base 10. The algorithm is identical, only changing the base from 2 to 10.
Add Binary with Constant Space (No Extra Array):
- Challenge: Compute the result without storing the entire result temporarily.
- Solution: Determine length of result first by simulating carry propagation without storing bits, then fill from the end. Tricky and not recommended.
Add Binary with Bitwise Operations on Strings:
- Challenge: Perform addition using only bitwise OR, AND, XOR on the string representations.
- Solution: Implement full adders on character arrays, essentially building the elementary addition logic manually.

Interview Cheat Sheet

First Steps:
1. Confirm input constraints (length, character set, leading zeros).
2. Ask about output format (canonical binary string).
3. Choose elementary addition unless the interviewer allows built-in conversion.
Talking Points:
- “Since strings can be up to 10^4 bits, we cannot convert to integers in languages with fixed-width integers, so we’ll simulate bit-by-bit addition.”
- “We start from the least significant bit (rightmost) because carries propagate leftward.”
- “We must handle the final carry and remove leading zeros.”
Testing:
- Test with provided examples.
- Test edge cases: both strings “0”, different lengths, carry propagates to new bit (e.g., “111”+“1”).
- Test large inputs (e.g., 10^4 ones + 10^4 ones).
Optimization Notes:
- Time is optimal (O(n)) because every bit must be examined.
- Space is optimal (O(n)) for the output, but we could reduce to (O(1)) extra space by writing directly into a preallocated string (if mutable).
Common Feedback:
- Interviewers appreciate clear variable names (carry, bit_a, bit_b).
- Mentioning the possibility of using divmod(total, 2) for conciseness is a plus.
- Discussing trade-offs between readability and micro-optimizations shows depth.

#67 - Add Binary

Add Binary

Problem Description

Solution

1. Problem Deconstruction (500+ words)

2. Intuition Scaffolding

3. Approach Encyclopedia

4. Code Deep Dive

5. Complexity War Room

6. Pro Mode Extras