C++: Add Binary

Thought Process

The problem requires adding two binary strings and returning the result as a binary string. To achieve this, we reverse both input strings to simplify the addition process starting from the least significant bit. We then iterate through the strings, adding corresponding bits along with any carry from the previous addition. The sum of the bits and the carry is used to determine the current bit of the result and the new carry. Finally, we reverse the result string to get the correct order. 

class Solution {
public:
    string addBinary(string a, string b) {
        
        reverse(a.begin(),a.end());
        reverse(b.begin(),b.end());

        string ansString;
        int aIdx=0;
        int bIdx=0;
        int carry=0;

        while(aIdx<a.size() || bIdx<b.size() || carry!=0){

            int aBit = (aIdx<a.size())? a[aIdx]-'0' : 0;
            int bBit = (bIdx<b.size())? b[bIdx]-'0' : 0;

            int sum = aBit + bBit + carry;
            int ansBit = sum%2;
            
            carry = sum/2;

            ansString.push_back(ansBit+'0');
            aIdx++;
            bIdx++;
        }
        reverse(ansString.begin(),ansString.end());
        return ansString;
    }
};

Code Complexity

Time Complexity: O(n)

The algorithm iterates through the longer of the two input strings once, making it linear in time complexity.

Space Complexity: O(n)

The algorithm uses additional space to store the result string, which is proportional to the input size.

Code copied!