Monday, November 25, 2013

LeetCode Problem : Add Binary

Problem


Given two binary strings, return their sum (also a binary string).
For example,
a = "11"
b = "1"
Return "100".

Code

string addBinary(string a, string b) {
    // IMPORTANT: Please reset any member data you declared, as
    // the same Solution instance will be reused for each test case.
    int m = a.size();
    int n = b.size();
    int i = 0,carry = 0;
    stack<int> st;
    while(i < m || i < n){
        int sum,num;
        if(i < m && i < n){
            sum = a[m -1 - i] - '0'+ b[n - 1 - i] - '0';
            ++i;
        }
        else if(i < m){
            sum = a[m - 1 - i] - '0';
            ++i;
        }
        else{
            sum = b[n - 1 - i] - '0';
            ++i;
        }
        sum += carry;
        num = sum%2;
        carry = sum / 2;
        st.push(num);
    }
    while(carry > 0){
        st.push(carry % 2);
        carry /= 2;
    }
    string result;
    while(!st.empty()){
        result += st.top() + '0';
        st.pop();
    }
    return result; 
}

No comments:

Post a Comment