Add Binary

Clarify the problem:

• The problem requires adding two binary strings and returning the sum as a binary string.
• The binary strings can have leading zeros.
• We need to implement a function that takes two binary strings as input and returns their sum as a binary string.

Analyze the problem:

• Input: Two binary strings.
• Output: The sum of the binary strings as a binary string.
• Constraints:
  • The length of the binary strings is between 1 and 10^4.
  • The binary strings can have leading zeros.

Design an algorithm:

• We can solve this problem by performing binary addition manually.
• We start from the rightmost bits and perform a binary addition.
• We keep track of the carry and add the corresponding bits from both strings along with the carry.
• We build the result string by appending the remainder of the sum to the left.
• If there is a carry after adding all the bits, we append it to the left as well.
• Finally, we return the resulting binary string.

Explain your approach:

• We will implement a function called addBinary that takes two binary strings as input.
• We initialize an empty string called result to store the resulting binary string.
• We initialize two pointers i and j to the rightmost bits of the input strings.
• We initialize a variable carry to keep track of the carry during addition.
• We iterate over the strings from right to left until both pointers reach the beginning of the strings.
• In each iteration, we convert the current bits at indices i and j to integers.
• We calculate the sum by adding the converted bits along with the carry.
• We update the carry based on the sum, and calculate the remainder by taking the sum modulo 2.
• We append the remainder to the left of the result string.
• After the iteration, if there is a remaining carry, we append it to the left of the result string.
• Finally, we return the resulting binary string.

Write clean and readable code:

python

def addBinary(a, b):
    result = ""
    i = len(a) - 1
    j = len(b) - 1
    carry = 0

    while i >= 0 or j >= 0:
        digit_a = int(a[i]) if i >= 0 else 0
        digit_b = int(b[j]) if j >= 0 else 0
        digit_sum = digit_a + digit_b + carry
        carry = digit_sum // 2
        remainder = digit_sum % 2
        result = str(remainder) + result
        i -= 1
        j -= 1

    if carry:
        result = str(carry) + result

    return result

Test your code:

python

# Test case 1
# Binary strings: "11" + "1"
# Sum: 3 in binary, which is "11"
# Expected output: "100"
assert addBinary("11", "1") == "100"

# Test case 2
# Binary strings: "1010" + "1011"
# Sum: 21 in binary, which is "10101"
# Expected output: "10101"
assert addBinary("1010", "1011") == "10101"

# Test case 3
# Binary strings: "0" + "0"
# Sum: 0 in binary, which is "0"
# Expected output: "0"
assert addBinary("0", "0") == "0"

Optimize if necessary:

• The provided solution is already straightforward and efficient.
• There is no need for further optimization.

Handle error cases:

• The code assumes that the input strings are valid binary strings.
• If the input strings are empty or contain characters other than '0' and '1', the behavior is undefined.

Discuss complexity analysis:

• Let n be the maximum length among the two input binary strings.
• The time complexity of the solution is O(n) since we iterate over the strings once.
• The space complexity is O(n) since we store the resulting binary string in the result variable.