class Solution {
public:
    string addBinary(string a, string b) {
        string res;
        int N1=a.size();
        int N2=b.size();
        int maxlength=N1>N2?N1:N2;
        reverse(a.begin(),a.end());
        reverse(b.begin(),b.end());
        int i=0;
        int sum=0;
        while(i<maxlength)
        {
            if(i<N1&&i<N2)
                sum+=((a[i]-'0')+(b[i]-'0'));
            else if(i<N1&&i>=N2)
                sum+=(a[i]-'0');
            else
                sum+=(b[i]-'0');
            res.push_back(sum%2+'0');
            sum=sum/2;
            i++;
        }
        if(sum>0)
            res.push_back(sum+'0');
        reverse(res.begin(),res.end());
        return res;
    }
};