Add Binary easy

Problem Statement

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"

Steps

1. Initialization: Initialize a variable carry to 0. This variable will store the carry-over bit from each addition. Initialize an empty string result to store the binary sum.

2. Iteration: Iterate through the strings a and b from right to left (least significant bit to most significant bit). If either string is shorter, treat the missing bits as 0.

3. Bitwise Addition: For each pair of bits (one from a and one from b), perform bitwise addition:

   • Convert the characters to integers (using int(char, 2)).
   • Calculate the sum sum = int(a_bit, 2) + int(b_bit, 2) + carry.
   • Update the carry: carry = sum // 2 (integer division).
   • Append the least significant bit of the sum to the result: result = str(sum % 2) + result.

4. Final Carry: After iterating through all bits, if carry is 1, append "1" to the beginning of the result.

5. Return: Return the result string.

Explanation

The algorithm simulates the process of adding binary numbers manually. We iterate through the bits from right to left, adding each pair of bits along with the carry from the previous addition. The % 2 operation extracts the least significant bit (the result of the addition for that position), and // 2 calculates the carry-over to the next position. The string is built in reverse because we start from the least significant bit.

Code

def addBinary(a, b):
    """
    Adds two binary strings and returns the sum as a binary string.

    Args:
        a: The first binary string.
        b: The second binary string.

    Returns:
        The sum of the two binary strings as a binary string.
    """
    max_len = max(len(a), len(b))
    a = a.zfill(max_len)  # Pad with leading zeros if necessary
    b = b.zfill(max_len)  # Pad with leading zeros if necessary

    carry = 0
    result = ""
    for i in range(max_len - 1, -1, -1):
        sum = int(a[i], 2) + int(b[i], 2) + carry
        carry = sum // 2
        result = str(sum % 2) + result
    if carry:
        result = "1" + result
    return result

Complexity

• Time Complexity: O(max(len(a), len(b))), as we iterate through the longer of the two strings once.
• Space Complexity: O(max(len(a), len(b))), in the worst case, to store the result string. The space used for carry is constant.