Add Binary

Problem:

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

For example,
a = "11"
b = "1"
Return "100".

Solution:


class Solution {
public:
    string addBinary(string a, string b) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
       string solution;
       int size1 = a.size() - 1, size2 = b.size() - 1;
       char carry;
     
       while (size1 >= 0 && size2 >= 0) {
           if (a[size1] == b[size2] && a[size1] != '0') {
                if (carry != '1') {
                    solution += '0';
                } else {
                    solution += '1';
                }
                carry = '1';
           }
           else if (a[size1] == '1') {
               if (b[size2] == '0')
                    if (carry == '1') {
                        solution += '0';
                        carry = '1';
                    } else {
                        solution += '1';
                    }
           } else {
                    if (carry == '1') {
                        if (b[size2] == '1') {
                            solution += '0';
                            carry = '1';
                        } else {
                            solution += '1';
                            carry = '0';
                        }
                    } else {
                        solution += b[size2];
                    }
           }
           size1--;
           size2--;
       }
       if (size2 >= 0 ) {
            size1 = size2;
            a = b;
       }
       while (size1 >= 0) {
               if (carry == '1') {
                   if (a[size1] == '1') {
                         solution += '0';
                        carry = '1';
                   } else {
                       solution += '1';
                       carry = '0';
                   }
               } else {
                   solution += a[size1];
               }
               size1--;
        }
        if (carry == '1')
            solution += carry;

        if (solution.size() > 1)
            reverse(solution);
     
        return solution;
    }
 
    void reverse(string &s) {
        int end = s.size() - 1, i = 0;
        for (i = 0; i < end;  i++,end--) {
            char temp = s[i];
            s[i] = s[end];
            s[end] = temp;
        }
    }
};

 ======== Second time =====
class Solution {
public:
    char oper(char a, char b, char *carry) {
        char to_ret;
        if (*carry == '1') {
            if (a == '1')
                if (b == '1') {
                    to_ret = '1';
                } else {
                    to_ret = '0';
                }
            else
                if (b == '1') {
                    to_ret = '0';
                } else {
                    to_ret = '1';
                    *carry = '0';
                }
        } else {
            if (a == '1')
                if (b == '1') {
                    to_ret = '0';
                    *carry = '1';
                } else {
                    to_ret = '1';
                }
            else
                if (b == '1') {
                    to_ret = '1';
                } else {
                    to_ret = '0';
                }
        }
        return to_ret;
                
    }
    
    char oper_on_remaining(char a, char *carry) {
        char to_ret;
        if (*carry == '1') {
            if (a == '1')
                to_ret = '0';
            else {
                to_ret = '1';
                *carry = '0';
            }
        } else {
            if (a == '1')
                to_ret = '1';
            else
                to_ret = '0';
        }
        return to_ret;
                
    }
    string addBinary(string a, string b) {
        string bigger;
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        
        int size_a = a.size();
        int size_b = b.size();
        
        if (size_a > size_b)
            bigger = a;
        else
            bigger = b;
        
        string sol(bigger);

        char carry = '0';        
        for (int i = 0; i < min(size_a, size_b); i++)
            sol[i] = oper(a[i], b[i], &carry);
        for (int i = min(size_a, size_b); i < max(size_a, size_b); i++)
            sol[i] = oper_on_remaining(bigger[i], &carry);
            
        if (carry == '1')
            sol.push_back(carry);
        reverse(sol.begin(), sol.end());
        return sol;
    }
};


====== Shorter solution ====

string addBinary(string a, string b) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      string result;  
5:      int maxL = a.size() > b.size()? a.size():b.size();  
6:      std::reverse(a.begin(), a.end());  
7:      std::reverse(b.begin(), b.end());  
8:      int carry=0;  
9:      for(int i =0; i<maxL;i++)  
10:      {  
11:        int ai = i<a.size()? a[i]-'0':0;  
12:        int bi = i<b.size()?b[i]-'0':0;  
13:        int val = (ai+bi+carry)%2;  
14:        carry = (ai+bi+carry)/2;  
15:        result.insert(result.begin(), val+'0');  
16:      }  
17:      if(carry ==1)  
18:      {  
19:        result.insert(result.begin(), '1');  
20:      }  
21:      return result;  
22:    }  

=== Third time =====
string addBinary(string a, string b) {
        string ans;
       
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
       
        int carry = 0, sum = 0, i = 0;
        while (i < a.size() || i < b.size()) {
            sum = (i < a.size() ? a[i] - '0': 0) +
                  (i < b.size() ? b[i] - '0': 0) +
                  carry;
            carry = sum / 2;
            ans += to_string(sum % 2);
            i++;
        }
        if (carry == 1) {
            ans += "1";
        }
       
        reverse(ans.begin(), ans.end());
        return ans;
    }

========== Best one ========

class Solution { public: string addBinary(string a, string b) { string str = ""; int i = a.size()-1, j = b.size()-1; int c=0; while(i>=0||j>=0||c==1) { c+=(i>=0)?a[i--]-'0':0; c+=(j>=0)?b[j--]-'0':0; str = char(c%2+'0')+str; c/=2; } return str; } };