### leetcode Question 4: Add binary

Given two binary strings, return their sum (also a binary string).
For example,
a = "11"
b = "1"
Return "100".

### Analysis:

This is an easy problem but needs carefulness.
Main idea has 2 steps:
1. Check the length of each string and add "0" to the shorter one.
2. Sum up the two strings, using a "carry" variable to store the carry.

Note that in Python, one can not assign value for specific char in a string, the list() operation is needed to change string into list of chars.

### Code(C++):

class Solution {
public:
string addBinary(string a, string b) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
string res = a.size()>b.size()?a:b;
string str = a.size()>b.size()?b:a;
bool carry=false;
int i=str.size()-1;
int j=res.size()-1;
while (i>=0){
if (res[j]=='1' && str[i]=='1'){res[j]=carry?'1':'0';carry=true;i--;j--;continue;}
if (res[j]=='0' && str[i]=='0'){res[j]=carry?'1':'0';carry=false;i--;j--;continue;}
if (res[j]=='0' && str[i]=='1'){res[j]=carry?'0':'1';i--;j--;continue;}
if (res[j]=='1' && str[i]=='0'){res[j]=carry?'0':'1';i--;j--;continue;}
}
while (j>=0 && carry){
if (res[j]=='1'){res[j]='0';j--;continue;}
if (res[j]=='0'){res[j]='1';break;}
}
if (j<0 && carry){ res="1"+res;}
return res;
}
};


### Code(Python):

class Solution:
# @param a, a string
# @param b, a string
# @return a string
if len(a) > len(b):
b = b.rjust(len(a), '0')
else:
a = a.rjust(len(b), '0')
a = list(a)
b = list(b)
carry = '0'
for i in xrange(len(a)-1,-1,-1):
if a[i] == '0' and b[i] == '0':
a[i] = carry
carry = '0'

elif a[i] == '1' and b[i] == '0':
if carry == '1':
a[i] = '0'
carry = '1'

elif a[i] == '0' and b[i] == '1':
if carry == '1':
a[i] = '0'
carry = '1'
else:
a[i] = '1'

elif a[i] == '1' and b[i] == '1':
if carry == '1':
a[i] = '1'
else:
a[i] = '0'
carry = '1'

if carry == '1':
a.insert(0, '1')

return ''.join(a)



1. If we have two bits a and b and previous carry
the new sum bit will be c= (a+b+carry)%2 and carry will be (a+b+carry)/2.
so, we can avoid some if else cases:

string addBinary(string a, string b) {
string big = a.size()>b.size()?a:b;
string small = a.size()>b.size()?b:a;
int i = big.size()-1;
int j = small.size()-1;
int carry=0;
while(j>=0){
int a = big[i]-'0';int b=small[j]-'0';
int c = (a+b+carry)%2;
carry = (a+b+carry)/2;
big[i]=c+'0';
i--;
j--;
}while(i>=0 && carry){
int a = big[i]-'0';
int c = (a+carry)%2;
carry = (a+carry)/2;
big[i]=c+'0';
i--;
}if(i<0 && carry)big = "1"+big;
return big;
}

2. class Solution:
# @param a, a string
# @param b, a string
# @return a string
if len(a)len(b):
for i in range(len(a)-len(b)):
b='0'+b
c=[]
for i in range(1,len(a)+1):
c.append(int(a[-i])+int(b[-i]))
for i in range(len(c)):
if c[i]>=2 and i!=(len(c)-1):
c[i]=c[i]-2
c[i+1]+=1
elif c[i]>=2 and i==(len(c)-1):
c[i]=c[i]-2
c.append(1)

a=''.join(map(str,c))
return a[::-1]

3. This comment has been removed by the author.

out = ""
carry = 0

if len(a)>len(b):
while len(a) > len(b):
b = "0"+b
else:
while(len(b)>len(a)):
a="0"+a
for i in reversed(range(len(a))):
out = str(int(a[i])^int(b[i])^int(carry))+out
carry = (int(a[i])and int(b[i])) or (int(a[i])and carry) or (int(b[i])and carry)
if carry == 1:
out = "1" + out

return out