Solution
To add a binary, the following rules apply:
num1 + num2 + carry = result + carry
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1
This table can simply be comprehended as below:
Case 1: num1 + num2 + carry < 2
result = num1 + num2 + carry
carry = 0
Case 2: num1 + num2 + carry >= 2
result = num1 + num2 + carry - 2
carry = 1
Note that this is exactly equal to decimal addition. Just replace 2 with 10 above. For that matter, these are the general rules for base-n addition (replace 2 with n above).
We start adding from the last digit (lowest significant digit) and then reverse our answer.
string addBinary(string a, string b) {
string ans = "";
int carry = 0;
for (int i=a.length()-1, j=b.length()-1; i>=0 || j>=0; i--, j--) {
int num1 = i>=0 ? a[i]-'0' : 0;
int num2 = j>=0 ? b[j]-'0' : 0;
if (num1 + num2 + carry >= 2) {
ans += num1+num2+carry-2+'0';
carry = 1;
} else {
ans += num1+num2+carry+'0';
carry = 0;
}
}
if (carry > 0)
ans += '1';
reverse(begin(ans), end(ans));
return ans;
}
Time complexity: O(max(m,n)) where m and n are lengths of the strings a and b respectively