An accepted concise Python recursive solution 10 lines


  • 34
    L
    #add two binary from back to front, I think it is very self explained, when 1+1 we need a carry.
       class Solution:
            def addBinary(self, a, b):
                if len(a)==0: return b
                if len(b)==0: return a
                if a[-1] == '1' and b[-1] == '1':
                    return self.addBinary(self.addBinary(a[0:-1],b[0:-1]),'1')+'0'
                if a[-1] == '0' and b[-1] == '0':
                    return self.addBinary(a[0:-1],b[0:-1])+'0'
                else:
                    return self.addBinary(a[0:-1],b[0:-1])+'1'

  • 0
    R
    This post is deleted!

  • 3
    R

    I used Python with bitwise solution. It can be found on cc150.
    The solution does not calculate carry digit by digit but use and("&") operator, which means, if two digits are "1", there must be a carry equals 1. But we need to left shift("<<") it because the carry is one digit higher.
    for the part not include carry, we can use XOR(^), 1^1 = 0, 1 + 1 = 10, without carry ,it is also "0".

    class Solution:
        # @param a, a string
        # @param b, a string
        # @return a string
        def addBinary(self, a, b):
            if a == "":
                return b
            if b == "":
                return a
            a_2 = int(a,2)
            b_2 = int(b,2)
            carry = 1
            while carry != 0:
                carry = (a_2 & b_2)<<1
                a_2 = a_2 ^ b_2
                b_2 = carry
            return bin(a_2)[2:]

  • 8
    W

    I think you answer can be simplified to:
    return bin(int(a, 2) + int(b, 2))[2:]


  • 0
    F

    Doesn't you encounter the problem of reaching maximum depth of recursion?


  • 0
    F

    Oh, my bad, it doesn't. Nvmd


  • 2
    M

    Thank you for your sharing! I think it can be more concise like the following (Actually, it's really an awesome answer! ):

    class Solution:
        def addBinary(self, a, b):
            if len(a)==0: return b
            if len(b)==0: return a
            if a[-1] == '1' and b[-1] == '1':
                return self.addBinary(self.addBinary(a[0:-1], b[0:-1]), '1') + '0'
            else:
                return self.addBinary(a[0:-1], b[0:-1]) + str(int(a[-1]) + int(b[-1]))

  • -1
    F

    @Meng-Ju I agree that the solution can be narrowed down to only three if statements, but I feel it would be better to take advantage of the fact that we can use bitwise operations:

        if len(a) == 0: return b
        if len(b) == 0: return a
        if int(a[-1]) & int(b[-1]):
            return self.addBinary(self.addBinary(a[0:-1], b[0:-1]), str(int(a[-1]) & int(b[-1]))) + str(int(a[-1]) ^ int(b[-1]))
        else:
            return self.addBinary(a[0:-1], b[0:-1]) + str(int(a[-1]) ^ int(b[-1]))

  • 0
    B

    @wenchao_hu
    it is cool

    at first, i use .repalce('0b', '') instead of [2:], it only beats 10%, i beat 75% when i use the latter..


  • 0
    Y

    How does it work when you put three arguments into two arguments functions?


  • 0
    L

    @yidong_w he used that function twice


  • 0
    A

    @wenchao_hu this may not be allowed in real interview


  • 0
    S
    This post is deleted!

  • 0
    S

    @richardli515 real bit manipulation solution, appreciate it.
    Also, lots of ppl said like "why not just using one line python with sth like bin() to get the accept ans?"
    Well, do you know what is that "+" mean?
    Learning Before Tricking.

    def addBinary(self, a, b):
            if not a or not b:
                return a or b
            a_2 = int(a,2)
            b_2 = int(b,2)
            carry = 1
            
            while carry != 0:
                carry = (a_2 & b_2)<<1 #carry
                a_2 = a_2 ^ b_2 #sum without carry
                b_2 = carry #for next carry calclation
            return "{0:b}".format(a_2)
    

Log in to reply
 

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