Problem Description

You are given two binary strings a and b (strings containing only '0' and '1' characters). Your task is to add these two binary numbers and return their sum as a binary string.

For example:

• If a = "11" (which represents 3 in decimal) and b = "1" (which represents 1 in decimal), the output should be "100" (which represents 4 in decimal).
• If a = "1010" and b = "1011", the output should be "10101".

The given solution takes a straightforward approach by converting the binary strings to integers, performing addition, and converting back to binary. It uses Python's built-in int(a, 2) to convert binary string a to an integer, adds the two integers together, then uses bin() to convert back to binary format. The [2:] slice removes the '0b' prefix that Python adds to binary representations.

The reference approach mentions using simulation with a carry variable and two pointers traversing from the end of both strings, which would manually perform binary addition bit by bit, similar to how you would add numbers on paper.

Intuition

When we need to add two binary numbers, we can think about how we normally add decimal numbers by hand - we start from the rightmost digit and work our way left, keeping track of any carry values.

For binary addition, the rules are simpler since we only have 0 and 1:

• 0 + 0 = 0
• 0 + 1 = 1
• 1 + 0 = 1
• 1 + 1 = 10 (which is 0 with a carry of 1)

We could simulate this process manually by iterating through both strings from right to left, adding corresponding bits along with any carry from the previous position. This would mimic the pencil-and-paper method of binary addition.

However, there's a much simpler approach: since Python (and most programming languages) already knows how to handle binary-to-decimal conversions and arithmetic operations, we can leverage built-in functions. We can convert both binary strings to their decimal equivalents using int(a, 2) and int(b, 2), perform regular integer addition, and then convert the result back to a binary string using bin().

This approach trades the manual bit-by-bit manipulation for the simplicity of using language features. While the manual simulation helps us understand the underlying process, the conversion approach gives us clean, concise code that accomplishes the same goal by letting Python handle the binary arithmetic internally.

Learn more about Math patterns.

Solution Approach

The reference solution mentions using simulation with a carry variable and two pointers. Let's walk through this bit-by-bit addition approach:

We initialize a carry variable to 0 and set two pointers i and j to point to the last characters of strings a and b respectively. We'll build our result string by processing bits from right to left, just like manual addition.

The algorithm works as follows:

1. Start from the rightmost positions: i = len(a) - 1 and j = len(b) - 1

2. While there are still bits to process or there's a carry:

   • Get the current bit from a if i >= 0, otherwise use 0
   • Get the current bit from b if j >= 0, otherwise use 0
   • Calculate the sum: current_sum = bit_a + bit_b + carry
   • The new bit for our result is current_sum % 2
   • The new carry is current_sum // 2
   • Move pointers left: i -= 1 and j -= 1

3. Build the result string by prepending each calculated bit

For example, adding "1010" and "1011":

• Position 0: 0 + 1 + 0 = 1, result bit = 1, carry = 0
• Position 1: 1 + 1 + 0 = 2, result bit = 0, carry = 1
• Position 2: 0 + 0 + 1 = 1, result bit = 1, carry = 0
• Position 3: 1 + 1 + 0 = 2, result bit = 0, carry = 1
• No more bits, but carry = 1, so add 1 to result

Final result: "10101"

The provided solution code takes a different, more concise approach by using Python's built-in conversion functions: int(a, 2) + int(b, 2) converts both binary strings to integers, adds them, then bin() converts back to binary. The [2:] slice removes the '0b' prefix that Python adds to binary representations.

Example Walkthrough

Let's walk through adding a = "101" and b = "11" using the bit-by-bit simulation approach:

Initial Setup:

• a = "101" (5 in decimal)
• b = "11" (3 in decimal)
• Expected result: "1000" (8 in decimal)
• Initialize: carry = 0, i = 2 (last index of a), j = 1 (last index of b)
• Result string starts empty: result = ""

Step 1: Process rightmost bits

• a[2] = '1' → bit_a = 1
• b[1] = '1' → bit_b = 1
• Sum = 1 + 1 + 0 (carry) = 2
• Result bit = 2 % 2 = 0
• New carry = 2 // 2 = 1
• Result = "0"
• Move pointers: i = 1, j = 0

Step 2: Process next bits

• a[1] = '0' → bit_a = 0
• b[0] = '1' → bit_b = 1
• Sum = 0 + 1 + 1 (carry) = 2
• Result bit = 2 % 2 = 0
• New carry = 2 // 2 = 1
• Result = "00"
• Move pointers: i = 0, j = -1

Step 3: Process remaining bit from a

• a[0] = '1' → bit_a = 1
• j < 0, so bit_b = 0
• Sum = 1 + 0 + 1 (carry) = 2
• Result bit = 2 % 2 = 0
• New carry = 2 // 2 = 1
• Result = "000"
• Move pointers: i = -1, j = -2

Step 4: Process final carry

• Both i < 0 and j < 0, but carry = 1
• Add carry to result
• Result = "1000"

Final Result: "1000"

Using the conversion approach from the provided solution:

• Convert: int("101", 2) = 5 and int("11", 2) = 3
• Add: 5 + 3 = 8
• Convert back: bin(8) = "0b1000"
• Remove prefix: "0b1000"[2:] = "1000"

Solution Implementation

Time and Space Complexity

The time complexity is O(m + n), where m and n are the lengths of strings a and b respectively. This is because:

• int(a, 2) converts string a to an integer, which requires traversing all m characters - O(m)
• int(b, 2) converts string b to an integer, which requires traversing all n characters - O(n)
• The addition of two integers takes O(max(m, n)) time in the worst case
• bin() conversion back to binary string takes O(max(m, n)) time as the result can be at most max(m, n) + 1 bits
• Overall: O(m) + O(n) + O(max(m, n)) = O(m + n)

The space complexity is O(max(m, n)). This is because:

• int(a, 2) creates an integer that requires O(m) bits of space
• int(b, 2) creates an integer that requires O(n) bits of space
• The sum creates an integer requiring up to O(max(m, n) + 1) bits
• bin() creates a new string of length O(max(m, n))
• The intermediate integer objects and the output string all contribute to the space complexity

Note: The reference answer states O(1) space complexity, which would be accurate if we only counted auxiliary space excluding the output. However, considering the intermediate integer representations and the output string, the actual space complexity is O(max(m, n)).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow in Other Languages

While the Python solution using int(a, 2) works seamlessly for arbitrarily large binary strings due to Python's unlimited integer precision, this approach would fail in languages like Java or C++ when dealing with binary strings longer than 32 or 64 bits. For instance, a binary string with 100 digits would cause integer overflow.

Solution: Implement the bit-by-bit addition algorithm with carry:

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

2. Forgetting to Handle Empty Strings

The current solution assumes both input strings are non-empty. If either a or b is an empty string, int("", 2) will raise a ValueError.

Solution: Add validation at the beginning:

def addBinary(self, a: str, b: str) -> str:
    if not a:
        return b if b else "0"
    if not b:
        return a
  
    return bin(int(a, 2) + int(b, 2))[2:]

3. Leading Zeros in Input

While the current solution handles leading zeros correctly (e.g., "0011" + "001" works fine), developers might unnecessarily try to strip leading zeros first, which could cause issues with edge cases like "0" + "0".

Solution: Trust the built-in functions to handle leading zeros properly, or if implementing manually, ensure the special case of all zeros is handled correctly.