Problem description:

Given two binary strings, return their sum (also a binary string).

The input strings are both non-empty and contains only characters 1 or 0.

Example 1:

Input: a = “11”, b = “1”
Output: “100”
Example 2:

Input: a = “1010”, b = “1011”
Output: “10101”

Solution:

The idea is to start from the end of string and add every bit.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def addBinary(self, a: str, b: str) -> str:
        i, j = len(a)-1, len(b)-1
        carry = 0
        res = ""
        
        while i >= 0 or j >= 0:
            x, y = 0, 0
            x = 1 if i >= 0 and a[i] == '1' else 0
            y = 1 if j >= 0 and b[j] == '1' else 0
            res = str((x+y+carry)%2) + res
            carry = (x+y+carry)//2
            i, j = i-1, j-1
        
        if carry:
            res = str(carry%2) + res
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    string addBinary(string a, string b) {
        int i= a.length()-1, j= b.length()-1, carry= 0;
        string res= "";
        while(i>=0 || j>= 0){
            int x= i>= 0 && a[i--]== '1';
            int y= j>= 0 && b[j--]== '1';
            res= to_string((x+y+carry)%2)+ res;
            carry= (x+y+carry)/2;
        }
        
        if(carry)
            res= to_string(carry)+res;
        return res;
    }
};

time complexity: $O(max(m, n))$
space complexity: $O(1)$

reference:
https://goo.gl/93GtDQ