A useful template when processing the "adding" questions


  • 0
    X

    Follow these four steps will give you a clear mind to solve this kind of problems.

    class Solution {
    public:
        string addBinary(string a, string b) {
            //safety
            if (a.empty()) return b;
            if (b.empty()) return a;
    
            // 1.pick the shorter one to align
            string shorter = (a.size() <= b.size())? a : b;
            string longer =  (a.size() > b.size())? a : b;
    
            auto itr_long = longer.rbegin();
            int carry = 0;
            int sum;
            // 2. calculate the overlay range
            for (auto itr = shorter.rbegin(); itr != shorter.rend(); ++itr, ++itr_long) {
                int sum = (*itr - '0') + (*itr_long - '0') + carry;
                carry = sum / 2;
                sum = sum % 2;
                *itr_long = sum + '0';
            }
            // 3. append / continue process the remaining
            for (; itr_long != longer.rend(); ++itr_long) {
                int sum = (*itr_long - '0') + carry;
                carry = sum / 2;
                sum = sum % 2;
                *itr_long = sum + '0';
            }
            // 4. lastly handle the overflow bit
            if (carry > 0) longer.insert(longer.begin(), '1');
    
            return longer;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.