Simplest iterative python using same logic as adding binary numbers by hand


  • 0
    S

    I don't like writing concise or obfuscated code. It makes it hard to read, understand and maintain. Could be done in lesser number of lines. Comments?

    class Solution(object):
        def addBinary(self, a, b):
            """
            :type a: str
            :type b: str
            :rtype: str
            """
            # mapping of sum of three binary numbers - carry from prev sum, bit of one number, bit of second number
            dic = {"000": ("0","0") , 
                   "001": ("0","1"), 
                   "010": ("0","1"), 
                   "011": ("1", "0"),
                   "100": ("0","1"), 
                   "101": ("1","0"), 
                   "110": ("1", "0"), 
                   "111": ("1","1")}
            
            mins,maxs = (a,b) if len(a) < len(b) else (b,a)
            
            carry = "0"
            ans   = ""
            i = len(mins) - 1
            j = len(maxs) - 1
            
            while i >= 0: # has something in small string to add
                carry, x = dic[mins[i] + maxs[j] + carry]
                ans += x
                i -= 1
                j -= 1
            
            while j >= 0: # has something in large string to add
                carry, x = dic["0" + maxs[j] + carry] # "0" replaces max[i], we ran out of bits in small string
                ans += x
                j -= 1
            
            if carry == "1": # got carry, append it
                ans += carry
            
            return ans[::-1] # reverse result
            
            # one liner python
            # return bin(int(a,2) + int(b,2))[2:]

Log in to reply
 

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