Python iterative solution - O(n) 66ms


  • 0
    G
    class Solution:
        # @param {string} a
        # @param {string} b
        # @return {string}
        def addBinary(self, a, b):
            i, m, n, result, carry = 1, len(a), len(b), [], 0
            while i <= m or i <= n:
                temp = carry
                if i <= m:
                    temp += int(a[-i])
                if i <= n:
                    temp += int(b[-i])
    
                carry = temp / 2
                result.append(str(temp % 2))
                i += 1
    
            if carry:
                result.append(str(carry))
    
            return ''.join(result[::-1])
    

    or a really short one if you want

    class Solution:
        # @param {string} a
        # @param {string} b
        # @return {string}
        def addBinary(self, a, b):
            return '{0:b}'.format(int(a, 2) + int(b, 2))

  • 0
    This post is deleted!

  • 0

    I don't think these solutions are "constant-space". The first one creates an extra list as large as the inputs, and the second one creates extra integers as large as the inputs.


  • 0
    C

    It seems the first iterative solution can be also coded as:

    def addBinary(self, a, b):
        res = ""
        carry = 0
        i, j = len(a)-1, len(b)-1
        while i >=0  or j >=0 or carry:
            val = carry
            if i >=0:
                val += int(a[i])
                i -= 1
            if j >=0:
                val += int(b[j])
                j -= 1
            res = str(val%2) + res
            carry = val//2
        return res

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.