# leetcode 67. Add Binary（python）

2022-01-29 18:03:24

This article has participated in 「 Digging force Star Program 」, Win a creative gift bag , Challenge creation incentive fund .

### describe

Given two binary strings a and b, return their sum as a binary string.

Example 1:

``````Input: a = "11", b = "1"
Output: "100"
Copy code ``````

Example 2:

``````Input: a = "1010", b = "1011"
Output: "10101"
Copy code ``````

Note:

``````1 <= a.length, b.length <= 10^4
a and b consist only of '0' or '1' characters.
Each string does not contain leading zeros except for the zero itself.
Copy code ``````

### analysis

According to the meaning , Two examples including 0 and 1 String of binary digits , The title requires us to add the literal binary codes represented by these two strings , Then the binary result returned is also represented by a string . In fact, this question is to investigate the basic operational logic of addition , Actually, it can be used python The built-in function of , But the idea is simple , Write your own code ：

• initialization M and N obtain a and b The length of two strings , Guarantee a It must be the larger string
• Then add them from the last bit , Full two, forward one
• Until the traversal is finished b All characters of , Maybe a There are also characters that need to be traversed , Continue to a The remaining characters are added above
• The string obtained at the end of traversal is the answer

``````class Solution(object):
def addBinary(self, a, b):
"""
:type a: str
:type b: str
:rtype: str
"""
M, N = len(a), len(b)
if M<N:
a,b = b,a
M,N = N,M
i,j = M-1,N-1
tmp = 0
result = ''
while i>-1 and j>-1:
c = int(a[i])+int(b[j])
if c + tmp > 1:
result = str(c+tmp-2) + result
tmp = 1
else:
result = str(c+tmp)+result
tmp = 0
i-=1
j-=1
while i>-1:
c = int(a[i]) + tmp
if c > 1:
result = str(c - 2) + result
tmp = 1
else:
result = str(c) + result
tmp = 0
i -= 1
if tmp>0:
result = '1' + result
return result

Copy code ``````

### Running results

``````Runtime: 45 ms, faster than 10.19% of Python online submissions for Add Binary.
Memory Usage: 13.5 MB, less than 50.08% of Python online submissions for Add Binary.
Copy code ``````

### analysis

The above code is easy to understand , But it's too redundant , The concise version is as follows .

• take a and b Convert to list a and b , Initialize carry variable tmp by 0 , result result Is an empty string

• When a Not empty or b Not empty or tmp When it's not empty ：

（1） When a Not empty tmp += int(a.pop())

（2） When b Not empty tmp += int(b.pop())

（3） And then tmp%2 The obtained number of this position is spliced to result front

（4）tmp Need Division 2

• At the end of the loop result Is the answer .

``````class Solution(object):
def addBinary(self, a, b):
"""
:type a: str
:type b: str
:rtype: str
"""
a = list(a)
b = list(b)
result = ''
tmp = 0
while a or b or tmp:
if a:
tmp += int(a.pop())
if b:
tmp += int(b.pop())
result = str(tmp%2) + result
tmp //= 2
return result
Copy code ``````

### Running results

``````Runtime: 29 ms, faster than 34.94% of Python online submissions for Add Binary.
Memory Usage: 13.6 MB, less than 50.08% of Python online submissions for Add Binary.
Copy code ``````

### analysis

Although I don't recommend using python The built-in function of , But when I use the above method to pass , I still feel itchy. I want to use the built-in function to solve it , Let's review the previous primary functions . Mainly used int Binary sum of bin Convert decimal integer to binary string result .

``````class Solution(object):
def addBinary(self, a, b):
"""
:type a: str
:type b: str
:rtype: str
"""
return  bin(int(a,2)+int(b,2))[2:]
Copy code ``````

### Running results

``````Runtime: 26 ms, faster than 48.42% of Python online submissions for Add Binary.
Memory Usage: 13.6 MB, less than 22.38% of Python online submissions for Add Binary.

Copy code ``````