67. Add Binary

Problem

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 1:

Input: a = "11", b = "1"
Output: "100"

Example 2:

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

Constraints:

• Each string consists only of '0' or '1' characters.
• 1 <= a.length, b.length <= 10^4
• Each string is either "0" or doesn't contain any leading zero.

Discussion

A problem very similar to 2. Add Two Numbers: Mathematical addition for binary numbers in string. As the input date is in binary string format, i try to keep the data type and handle the addition by conditional cases.

Solution

Similar to 2. Add Two Numbers, we have to handle:

1. When two numbers have different numbers of significant figures,
2. When carry digits exist in the addition,
3. When the most significant figures of the sum is carry.

Solving 1, when there is 1 binary string running out of characters during addition, we proceed the addition with the missing digits replaced by "0".

Handling the addition, we view it as string conditional cases:

Hence we can conclude:

1. When string A equals string B (case 1 - 2, 7 - 8), we can see the result digit equals to carry, while the result digit's equals string A and string B's value,
2. When string A does not equals string B (case 3 - 6), we can see the result dominated by carry. When carry is "0", result becomes "1"; when carry is "1", result becomes "10".

Hence we apply this logic in the additional handling. And after the handling of 2 and 3, the solution completes.

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        result = ''
        is_carry_exist = False

        size_a, size_b = len(a), len(b)
        n = max(size_a, size_b)

        for i in range(n):
            val_a = a[size_a - i - 1] if size_a > i else '0'
            val_b = b[size_b - i - 1] if size_b > i else '0'

            if val_a == val_b:
                if is_carry_exist:
                    result = '1' + result
                else:
                    result = '0' + result

                is_carry_exist = (val_a == '1' and val_b == '1')

            if val_a != val_b:
                if is_carry_exist:
                    result = '0' + result
                else:
                    result = '1' + result

        if is_carry_exist:
            result = '1' + result

        return result

Complexity Analysis

• Time Complexity: O(max(m, n)), wheres m and n are the size of the two input binary string. As only one looping through the larger binary string is required.
• Space Complexity: O(max(m, n)), as the result binary string's size is determined by the larger input binary string.