67.Add Binary

Tags: [implementation], [binary]

Com: {fb}

Link: https://leetcode.com/problems/add-binary/#/description

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

For example,
a ="11"
b ="1"
Return"100".

Solution:

class Solution(object):
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        if not a:
            return b
        if not b:
            return a

        result = []
        carry = 0

        a_index = len(a) - 1
        b_index = len(b) - 1

        while a_index >= 0 and b_index >= 0:
            curr_a = int(a[a_index])
            curr_b = int(b[b_index])
            tmp_sum = curr_a + curr_b + carry
            if tmp_sum >= 2:
                carry = tmp_sum / 2
            else:
                carry = 0

            result.append(tmp_sum % 2)
            a_index -= 1
            b_index -= 1

        while a_index >= 0:
            curr_a = int(a[a_index])
            tmp_sum = curr_a + carry
            if tmp_sum >= 2:
                carry = tmp_sum / 2
            else:
                carry = 0

            result.append(tmp_sum % 2)
            a_index -= 1

        while b_index >= 0:
            curr_b = int(b[b_index])
            tmp_sum = curr_b + carry
            if tmp_sum >= 2:
                carry = tmp_sum / 2
            else:
                carry = 0

            result.append(tmp_sum % 2)
            b_index -= 1

        if carry:
            result.append(carry)

        result.reverse()
        return ''.join([str(x) for x in result])

Revelation:

• Whatever the tmp_sum is >= 2 or not, we can just do result.append(tmp_sum % 2), because for example, tmp_sum = 3, tmp_sum % 2 = 1, and tmp_sum = 1, the tmp_sum % 2 = 1. So here we don't need to distinguish tmp_sum >= 2 or not.

Note:

• Time complexity = O(n), n is the max(len(a), len(b)).

My Own Follow Up:

• What about the input is negative binary numbers?
• Answer: Assume we are dealing with the 32 bits integers, we can still use the above algorithm to deal with the negative numbers, but at the last step, we need to check if the len(result binary str) <= 32, we just return this binary sting, but if its length is greater than 32, we should only return the right part of it, make it fit 32 bits.

reference: http://mathforum.org/library/drmath/view/55924.html