menu

[LeetCode] 067. Add Binary

Problem (Easy)

067. Add Binary

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”

Approach 1: (My Solution - Convert to Numbers)

Idea

  • Convert a and b to numbers;
  • Add two numbers;
  • Convert the result back to string and slice.

Solution

class Solution1:
    def addBinary(self, a, b): 
        """ 
        :type a: str
        :type b: str
        :rtype: str
        """
        return bin(int(a, 2) + int(b, 2))[2:]

Complexity

  • Time: $O(n)$
  • Space: $O(n)$

Approach 2: (My Solution - Operate Directly)

Idea

  • Loop adding operation bit by bit from right to left;
  • Use the divmod method.

Solution

class Solution2:
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        a, b = sorted((a,b), key=len)
        inc, res = 0, ''
        for i in range(len(b)):
            if i < len(a):
                inc, tmp = divmod(int(b[-1-i]) + int(a[-1-i]) + inc, 2)
                res = str(tmp) + res
            else:
                inc, tmp = divmod(int(b[-1-i]) + inc, 2)
                res = str(tmp) + res
        if inc:
            res = '1' + res 
        return res

Complexity

  • Time: $O()$
  • Space: $O()$



KF

Comments