C++ solution using simple math


#1

string Solution::addBinary(string A, string B) {
int n = A.length();
int m = B.length();
if(n > m){
while(A.length() != B.length()){
B = ‘0’ + B;
}
}
if(m > n){
while(A.length() != B.length()){
A = ‘0’ + A;
}
}
// cout<<A<<" “;
// cout<<B<<” ";
int carry = 0;
int a = A.length() - 1;
int b = B.length() - 1;
string ans;
while(a >= 0){
if(A[a]== ‘1’ && B[b] == ‘1’ && carry == 1){
ans = ‘1’ + ans;
}
else if(A[a] == ‘1’ && B[b] == ‘1’ && carry == 0){
ans = ‘0’ + ans;
carry = 1;
}
else if((A[a] == ‘1’ || B[b] == ‘1’) && carry == 1){
ans = ‘0’ + ans;
}
else if((A[a] == ‘1’ || B[b] == ‘1’) && carry == 0){
ans = ‘1’ + ans;
}
else if((A[a] == ‘0’ && B[a] == ‘0’) && carry == 1){
ans = ‘1’ + ans;
carry = 0;
}
else if((A[a] == ‘0’ && B[a] == ‘0’) && carry == 0){
ans = ‘0’ + ans;
}
a–;
b–;
}
if(carry == 1)
ans = ‘1’ + ans;
return ans;
}


#2

Simplest solution I could think of-

string Solution::addBinary(string A, string B) {
   string ans="";
   int i=A.length()-1,j=B.length()-1,a=0,b=0,sum=0,carry=0;
   while(i>=0 || j>=0){
        i>=0?a=A[i]-'0':a=0;
        j>=0?b=B[j]-'0':b=0;
    sum=(a+b+carry);
    ans.push_back(sum%2+'0');
    carry=sum/2;

    i--,j--;
   }
   if(carry)
   ans.push_back('1');
   
   reverse(ans.begin(),ans.end());
   
return ans;
}

#3

Complexity: O(n2)

    char get_xor(char x, char y)
    { return (x==y)?'0':'1'; }

    char get_and(char x, char y)
    { return (x=='1' && y=='1')?'1':'0'; }

    char get_or(char x, char y)
    { return (x=='0' && y=='0')?'0':'1'; }

    string Solution::addBinary(string A, string B) 
    {
        string res("");
        int i = A.size()-1, j = B.size()-1;
        char a, b, carry = '0';
        while(i>=0 || j>=0)
        {
            a = (i<0 || (A[i]!='0' && A[i]!='1')) ? '0' : A[i];
            b = (j<0 || (B[j]!='0' && B[j]!='1')) ? '0' : B[j];
            
            res = get_xor(get_xor(a, b), carry) + res;
            carry = get_or(get_and(a, b), get_and(carry, get_xor(a, b)));
            
            i--; 
            j--;
        }
        if(carry == '1')
            res = carry + res;
        return res;
    }