Easy and Intuitive O(n) C++ solution


#1

string Solution::addBinary(string A, string B) {
int n=A.length();
int m=B.length();
string res="";
if(m<n)
{
for(int i=0;i<n-m;i++)
B.insert(B.begin(),‘0’);
m=n;
}
else if(n<m)
{
for(int i=0;i<m-n;i++)
A.insert(A.begin(),‘0’);
n=m;
}
int i=n-1,j=m-1,carry=0,k=0;
while(i>=0 && j>=0)
{
if(A[i]-‘0’==0 && B[j]-‘0’==0)
{
if(carry==0)
res+=‘0’;
else
res+=‘1’;
carry=0;
}
else if(A[i]-‘0’==0 && B[j]-‘0’==1)
{
if(carry==0)
{
res+=‘1’;
carry=0;
}
else
{
res+=‘0’;
carry=1;
}
}
else if(A[i]-‘0’==1 && B[j]-‘0’==0)
{
if(carry==0)
{
res+=‘1’;
carry=0;
}
else
{
res+=‘0’;
carry=1;
}
}
else if(A[i]-‘0’==1 && B[j]-‘0’==1)
{
if(carry==0)
res+=‘0’;
else
res+=‘1’;
carry=1;
}
i–; j–;
}
if(carry==1)
res+=‘1’;
reverse(res.begin(),res.end());
return res;
}