Add Binary - Leetcode Solution

Problem Statement:

Given two binary strings, return their sum (also a binary string).

The input strings are both non-empty and contains only characters 1 or 0.

Example:

Input: a = "1010", b = "1011" Output: "10101"

Explanation: 1010 1011

---

10101

Solution:

For the given problem, we can take two pointers starting from the end of the binary strings a and b, to calculate the sum bit by bit, and then carry the remainder to the next bit. If the sum is greater than 1, (1+1) would indicate that a carry (1) is required for the next bit.

Algorithm:

1. Start from the last digit of both the strings.
2. Initialize three variables to store carry, sum and result.
3. Traverse the strings from the end to the start.
4. Calculate the sum of bits at the current index, carry and the previous carry.
5. If the sum is 0 or 1, update the carry to 0 and the sum to the value of the sum.
6. If the sum is 2 or 3, update the carry to 1 and the sum to the remainder of the sum/2.
7. Append the sum to the result string.
8. If there is still a carry remaining after the loop iteration, append it to the result.
9. Reverse the resultant string and return the answer.

A code snippet in Python is given below:

def addBinary(a: str, b: str) -> str:
    i, j = len(a)-1, len(b)-1
    carry, res = 0, ''
    while i >= 0 or j >= 0:    
        cur_sum = carry
        if i >= 0:
            cur_sum += int(a[i])
            i -= 1
        if j >= 0:
            cur_sum += int(b[j])
            j -= 1
        if cur_sum < 2:
            carry = 0
            res += str(cur_sum)
        else:
            carry = 1
            res += str(cur_sum % 2)
    if carry:
        res += str(carry)
    return res[::-1]

Time Complexity: O(n), where n is the length of the longest input string.

Space Complexity: O(n), where n is the length of the resultant string.

1