Solution Explanation for Add Binary

This problem asks to add two binary strings and return the sum as a binary string. Several approaches can solve this, but we'll focus on the most common and efficient method: simulation.

Approach: Simulation

The simulation approach mimics how we add binary numbers manually. We iterate through the strings from right to left (least significant bit to most significant bit), adding bits and handling carries.

1. Initialization: We use pointers i and j to track our position in strings a and b respectively, both initialized to the last index. A carry variable keeps track of the carry-over from the previous addition (initialized to 0). We use a string builder (or a list in Python) to efficiently construct the result string.

2. Iteration: The loop continues as long as there are bits left to process in either a or b, or if a carry is present.

3. Bit Addition: Inside the loop, we add the current bits from a and b (or 0 if the pointer is out of bounds) along with the carry.

4. Carry Handling: The sum is then divided by 2 to determine the new carry (integer division) and the remainder is the current bit of the result (which is appended to the result string).

5. Reversal: Since we added bits from right to left, the resulting string needs to be reversed before returning.

Time and Space Complexity

• Time Complexity: O(max(m, n)), where m and n are the lengths of strings a and b. We iterate through the strings once.
• Space Complexity: O(1). We use a constant amount of extra space for variables (i, j, carry, the result string builder). The result string itself has a length proportional to max(m,n), but that isn't considered extra space in this context.

Code Examples

The following code snippets demonstrate the simulation approach in several programming languages:

Python3

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        result = []
        i, j, carry = len(a) - 1, len(b) - 1, 0
        while i >= 0 or j >= 0 or carry:
            sum_bits = carry
            if i >= 0:
                sum_bits += int(a[i])
                i -= 1
            if j >= 0:
                sum_bits += int(b[j])
                j -= 1
            carry = sum_bits // 2
            result.append(str(sum_bits % 2))
        return "".join(result[::-1])
 

Java

class Solution {
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int i = a.length() - 1, j = b.length() - 1, carry = 0;
        while (i >= 0 || j >= 0 || carry > 0) {
            int sum = carry;
            if (i >= 0) {
                sum += a.charAt(i--) - '0';
            }
            if (j >= 0) {
                sum += b.charAt(j--) - '0';
            }
            sb.append(sum % 2);
            carry = sum / 2;
        }
        return sb.reverse().toString();
    }
}

C++

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

These examples follow the same logic, adapting syntax and data structures to each language. The core algorithm remains consistent, offering an efficient and understandable solution to the Add Binary problem. Note that other languages like Javascript, Go, or Rust would exhibit a similar structure.