Add Binary

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

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

Problem link

Solution

  • calculate from right to left
class Solution {
public:
    string addBinary(string a, string b) {
        if (a.empty()) return b;
        if (b.empty()) return a;
        int m = a.size();
        int n = b.size();
        string c;
        bool carry=false;
        int i,j;
        int sum;
        for (i=m-1, j=n-1; i>=0 && j>=0; --i, --j){
            sum = a[i]-'0' + b[j]-'0' + carry;
            carry = sum/2? true:false;
            c = to_string(sum%2) + c;
        }
        if (j>=0){ // run out of a
            for (; j>=0; --j){
                sum = b[j]-'0' + carry;
                carry = sum/2? true:false;
                c = to_string(sum%2) + c;
            }
        }else if (i>=0){ // run out of b
            for (; i>=0; --i){
                sum = a[i]-'0' + carry;
                carry = sum/2? true:false;
                c = to_string(sum%2) + c;
            }
        }
        if (carry==1){
            c = "1" + c;
        }
        return c;
    }
};
Advertisements
Add Binary

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s