algoadvance

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

Clarifying Questions

1. What is the maximum length of the binary strings?
   • The problem typically doesn’t specify, but we can assume standard input size constraints (~10^4 elements).
2. Do we need to handle invalid binary strings as input?
   • For the scope of this problem, we can assume the input strings are always valid binary strings.
3. Is it guaranteed that the input strings a and b are non-empty?
   • Yes, we will assume non-empty strings as per standard problem constraints.

Strategy

1. Initialize a result string to build the final binary sum.
2. Use two pointers starting from the end of each string a and b.
3. Use a carry variable to handle values that exceed 1 (carry over in binary addition).
4. Iterate over the strings from the end to the start, adding corresponding digits along with the carry.
5. Append the result of the addition (mod 2) to the result string and update the carry.
6. If there is still a carry after the loop, append it to the result.
7. Reverse the result string (since it was constructed backwards) and return it.

Code

def addBinary(a: str, b: str) -> str:
    i, j = len(a) - 1, len(b) - 1
    carry = 0
    result = []
    
    while i >= 0 or j >= 0 or carry:
        # get current digits
        x = int(a[i]) if i >= 0 else 0
        y = int(b[j]) if j >= 0 else 0
        
        # calculate sum and new carry
        total = x + y + carry
        carry = total // 2
        result.append(str(total % 2))
        
        # move pointers
        i -= 1
        j -= 1
    
    # reverse result since we've constructed it in reverse order
    return ''.join(result[::-1])

# Example usage
a = "1010"
b = "1011"
print(addBinary(a, b))  # Output: "10101"

Time Complexity

• Time Complexity: O(max(n, m)), where n and m are the lengths of the strings a and b respectively. This is because we iterate through both strings once.
• Space Complexity: O(max(n, m)), as we store the resulting sum in a list, which will be at most max(n, m) + 1 in length considering the carry.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?