[Easy] 67. Add Binary

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

Examples

Example 1:

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

Example 2:

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

Constraints

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

Clarification Questions

Before diving into the solution, here are 5 important clarifications and assumptions to discuss during an interview:

Binary addition: What are the addition rules? (Assumption: Standard binary addition - 0+0=0, 0+1=1, 1+1=10 (carry 1))
Input format: How are numbers represented? (Assumption: Binary strings - “101” represents 5 in decimal)
Return format: What should we return? (Assumption: Binary string representing sum of two binary numbers)
Leading zeros: Should we include leading zeros? (Assumption: No - per constraints, no leading zeros except for “0” itself)
Carry handling: How should we handle carry? (Assumption: Carry propagates from right to left - standard binary addition)

Interview Deduction Process (10 minutes)

Step 1: Brute-Force Approach (2 minutes)

Initial Thought: “I need to add binary numbers. Let me convert to decimal, add, convert back.”

Naive Solution: Convert both binary strings to integers, add them, convert result back to binary string.

Complexity: O(m + n) time, O(1) space

Issues:

May overflow for large numbers
Doesn’t work for very long strings
Not the intended approach
Loses binary manipulation practice

Step 2: Semi-Optimized Approach (3 minutes)

Insight: “I should add digit by digit from right to left, handling carry.”

Improved Solution: Process strings from right to left. Add corresponding digits along with carry. Build result string from right to left, reverse at end.

Complexity: O(max(m, n)) time, O(max(m, n)) space

Improvements:

Digit-by-digit addition is correct
Handles carry properly
Works with binary strings directly
O(max(m, n)) time is optimal

Step 3: Optimized Solution (5 minutes)

Final Optimization: “Digit-by-digit approach is optimal. Can optimize carry calculation.”

Best Solution: Process from right to left, add digits with carry. Use (a + b + carry) % 2 for result digit, (a + b + carry) / 2 for new carry. Build result efficiently.

Complexity: O(max(m, n)) time, O(max(m, n)) space

Key Realizations:

Digit-by-digit addition is correct approach
O(max(m, n)) time is optimal
Carry propagation is straightforward
Handle different string lengths naturally

Solution 1: Optimized Single Pass (Recommended)

Time Complexity: O(max(m, n)) where m and n are lengths of a and b
Space Complexity: O(max(m, n)) for the result string

This solution ensures the longer string is processed first, and uses a single carry variable that accumulates both digits efficiently.

class Solution {
public:
    string addBinary(string a, string b) {
        int n = a.size(), m = b.size();
        if(n < m)
            return addBinary(b, a);
        
        string rtn;
        int carry = 0, j = m - 1;
        
        for(int i = n - 1; i >= 0; i--) {
            if (a[i] == '1') carry++;
            if(j >= 0 && b[j--] == '1') carry++;
            rtn.push_back((carry % 2) ? '1': '0');
            carry /= 2;
        }
        
        if(carry == 1) rtn.push_back('1');
        reverse(rtn.begin(), rtn.end());
        return rtn;
    }
};

How Solution 1 Works

Ensure longer string first: If a is shorter, swap to process longer string first
Process from right to left: Start from least significant bit (end of strings)
Accumulate carry:
- Add 1 to carry if current bit in a is ‘1’
- Add 1 to carry if current bit in b is ‘1’ (if available)
Calculate result digit: carry % 2 gives the result bit (0 or 1)
Update carry: carry /= 2 gives the new carry (0 or 1)
Handle final carry: If carry remains after processing all bits, add ‘1’
Reverse result: Since we built it from right to left, reverse to get correct order

Key Insight

The carry variable accumulates both digits:

carry can be 0, 1, 2, or 3 (0+0, 0+1, 1+1, 1+1+carry)
carry % 2 gives the result bit
carry / 2 gives the new carry (always 0 or 1 for binary)

Solution 2: Standard Two-Pointer Approach

Time Complexity: O(max(m, n))
Space Complexity: O(max(m, n))

This is the more traditional approach that processes both strings simultaneously.

class Solution {
public:
    string addBinary(string a, string b) {
        string result;
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;
        
        while (i >= 0 || j >= 0 || carry) {
            int sum = carry;
            if (i >= 0) {
                sum += a[i] - '0';
                i--;
            }
            if (j >= 0) {
                sum += b[j] - '0';
                j--;
            }
            result.push_back((sum % 2) + '0');
            carry = sum / 2;
        }
        
        reverse(result.begin(), result.end());
        return result;
    }
};

How Solution 2 Works

Two pointers: i for string a, j for string b
Process while either string has digits or carry exists
Calculate sum: Add carry + digit from a (if available) + digit from b (if available)
Append result: sum % 2 gives the bit, convert to character
Update carry: sum / 2 gives the new carry
Reverse result: Built from right to left, so reverse at the end

Solution 3: Using Built-in Conversion (Not Recommended for Interviews)

Time Complexity: O(max(m, n))
Space Complexity: O(max(m, n))

This approach uses language built-ins to convert, add, and convert back. Not recommended for interviews but useful for quick solutions.

class Solution {
public:
    string addBinary(string a, string b) {
        // Convert binary strings to integers
        long long num1 = stoll(a, nullptr, 2);
        long long num2 = stoll(b, nullptr, 2);
        
        // Add and convert back to binary
        long long sum = num1 + num2;
        if (sum == 0) return "0";
        
        string result;
        while (sum > 0) {
            result.push_back((sum % 2) + '0');
            sum /= 2;
        }
        reverse(result.begin(), result.end());
        return result;
    }
};

Note: This approach has limitations:

May overflow for very large binary strings (beyond long long range)
Not suitable for interview settings where manual bit manipulation is expected
Useful for quick prototyping or when constraints guarantee small inputs

Solution 4: Bit Manipulation Style

Time Complexity: O(max(m, n))
Space Complexity: O(max(m, n))

A variation that explicitly handles bit operations.

class Solution {
public:
    string addBinary(string a, string b) {
        string result;
        int i = a.size() - 1, j = b.size() - 1;
        int carry = 0;
        
        while (i >= 0 || j >= 0 || carry) {
            int bit1 = (i >= 0) ? (a[i--] - '0') : 0;
            int bit2 = (j >= 0) ? (b[j--] - '0') : 0;
            
            int sum = bit1 + bit2 + carry;
            result.push_back((sum & 1) + '0');  // sum % 2 using bitwise AND
            carry = sum >> 1;  // sum / 2 using right shift
        }
        
        reverse(result.begin(), result.end());
        return result;
    }
};

Key Differences

Uses bitwise AND (& 1) instead of modulo for getting the bit
Uses right shift (>> 1) instead of division for carry
More explicit about bit operations

Example Walkthrough

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

Solution 1 (Optimized):

a = "1010" (longer, n=4)
b = "1011" (shorter, m=4, j=3)

i=3: a[3]='0', b[3]='1' → carry=1 → result='1', carry=0
i=2: a[2]='1', b[2]='1' → carry=2 → result='0', carry=1
i=1: a[1]='0', b[1]='0' → carry=1 → result='1', carry=0
i=0: a[0]='1', b[0]='1' → carry=2 → result='0', carry=1

Final carry=1 → result='1'
Reverse: "10101"

Solution 2 (Standard):

a = "1010", b = "1011"
i=3, j=3, carry=0

Step 1: sum=0+0+1=1 → result='1', carry=0
Step 2: sum=0+1+1=2 → result='0', carry=1
Step 3: sum=1+0+0=1 → result='1', carry=0
Step 4: sum=1+1+0=2 → result='0', carry=1
Step 5: carry=1 → result='1'

Reverse: "10101"

Complexity Analysis

Solution	Time	Space	Notes
Solution 1 (Optimized)	O(max(m,n))	O(max(m,n))	Ensures longer string processed first
Solution 2 (Standard)	O(max(m,n))	O(max(m,n))	Traditional two-pointer approach
Solution 3 (Built-in)	O(max(m,n))	O(max(m,n))	May overflow for large inputs
Solution 4 (Bitwise)	O(max(m,n))	O(max(m,n))	Explicit bit operations

Edge Cases

Different lengths: "1" + "111" → "1000"
Carry at end: "1" + "1" → "10"
All zeros: "0" + "0" → "0"
One empty: Not possible per constraints, but handled by j >= 0 check
Large strings: Up to 10^4 characters each

Common Mistakes

Forgetting final carry: Not adding carry if it remains after processing all bits
Wrong order: Not reversing the result string
Index out of bounds: Not checking if pointers are valid before accessing
Character conversion: Forgetting to convert between char and int ('0' vs 0)
Carry calculation: Using wrong formula for carry (should be sum / 2 not sum - 2)

Key Insights

Binary addition rules:
- 0 + 0 = 0 (carry 0)
- 0 + 1 = 1 (carry 0)
- 1 + 1 = 0 (carry 1)
- 1 + 1 + 1 = 1 (carry 1)
Carry propagation: Carry can only be 0 or 1 in binary addition
String processing: Process from right to left (least significant to most significant)
Result building: Build result backwards, then reverse

Optimization Tips

Pre-allocate space: Can reserve max(m, n) + 1 for result string
Early termination: If both strings exhausted and carry is 0, can break early
In-place modification: Could modify one string in-place, but not recommended for clarity

2. Add Two Numbers - Add numbers represented as linked lists
415. Add Strings - Add decimal number strings
43. Multiply Strings - Multiply number strings
66. Plus One - Add one to number array
989. Add to Array-Form of Integer - Add number to array-form integer

Pattern Recognition

This problem demonstrates the “String Arithmetic with Carry” pattern:

Process strings from right to left (least to most significant)
Handle different lengths gracefully
Track carry through iterations
Build result backwards, reverse at end
Handle final carry if exists

Real-World Applications

Binary Arithmetic: Core operation in computer arithmetic
Cryptography: Binary operations in encryption algorithms
Network Protocols: Checksum calculations
Error Detection: Parity bit calculations
Digital Circuits: Hardware adder implementations

Robina Li

[Easy] 67. Add Binary

[Easy] 67. Add Binary

Examples

Constraints

Clarification Questions

Interview Deduction Process (10 minutes)

Step 1: Brute-Force Approach (2 minutes)

Step 2: Semi-Optimized Approach (3 minutes)

Step 3: Optimized Solution (5 minutes)

Solution 1: Optimized Single Pass (Recommended)

How Solution 1 Works

Key Insight

Solution 2: Standard Two-Pointer Approach

How Solution 2 Works

Solution 3: Using Built-in Conversion (Not Recommended for Interviews)

Solution 4: Bit Manipulation Style

Key Differences

Example Walkthrough

Solution 1 (Optimized):

Solution 2 (Standard):

Complexity Analysis

Edge Cases

Common Mistakes

Key Insights

Optimization Tips

Pattern Recognition

Real-World Applications

Related Posts

Recent Posts

[Easy] 67. Add Binary

Examples

Constraints

Clarification Questions

Interview Deduction Process (10 minutes)

Step 1: Brute-Force Approach (2 minutes)

Step 2: Semi-Optimized Approach (3 minutes)

Step 3: Optimized Solution (5 minutes)

Solution 1: Optimized Single Pass (Recommended)

How Solution 1 Works

Key Insight

Solution 2: Standard Two-Pointer Approach

How Solution 2 Works

Solution 3: Using Built-in Conversion (Not Recommended for Interviews)

Solution 4: Bit Manipulation Style

Key Differences

Example Walkthrough

Solution 1 (Optimized):

Solution 2 (Standard):

Complexity Analysis

Edge Cases

Common Mistakes

Key Insights

Optimization Tips

Related Problems

Pattern Recognition

Real-World Applications

Related Posts

Recent Posts