LC-0067 Easy LeetCode

67. Add Binary

Read the full problem statement on LeetCode.

Difficulty: easy Acceptance: 56% Topics: Math, String, Bit Manipulation, Simulation

Reading material

Math & Geometry 12 min Strings 12 min Bit Manipulation 10 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)

class Solution(object):
    # @param a, a string
    # @param b, a string
    # @return a string
    def addBinary(self, a, b):
        result, carry, val = "", 0, 0
        for i in xrange(max(len(a), len(b))):
            val = carry
            if i < len(a):
                val += int(a[-(i + 1)])
            if i < len(b):
                val += int(b[-(i + 1)])
            carry, val = divmod(val, 2)
            result += str(val)
        if carry:
            result += str(carry)
        return result[::-1]


# Time:  O(n)
# Space: O(1)
from itertools import izip_longest


class Solution2(object):
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        result = ""
        carry = 0
        for x, y in izip_longest(reversed(a), reversed(b), fillvalue="0"):
            carry, remainder = divmod(int(x)+int(y)+carry, 2)
            result += str(remainder)
        
        if carry:
            result += str(carry)
        
        return result[::-1]

Solution from kamyu104/LeetCode-Solutions · MIT