EASY

Add Binary

Given two binary strings a and b, return their sum as a binary string.

Example

Input:

a = "11", b = "1"

Output:

"100"

Explanation: 11 (3 in decimal) + 1 (1 in decimal) = 100 (4 in decimal)

Constraints

1 ≤ a.length, b.length ≤ 10^4
a and b consist only of '0' or '1' characters.

Solution: Simulation

Time Complexity: O(max(n, m))
Space Complexity: O(max(n, m))

C++

class Solution {
public:
    string addBinary(string a, string b) {
        string res = "";
        int i = a.size() - 1, j = b.size() - 1, carry = 0;
        while (i >= 0 || j >= 0 || carry) {
            int sum = carry;
            if (i >= 0) sum += a[i--] - '0';
            if (j >= 0) sum += b[j--] - '0';
            res += (sum % 2) + '0';
            carry = sum / 2;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};