67. Add Binary

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

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

    string addBinary(string a, string b) {
        int carry = 0;
        vector<char> num{'0', '1'};
        string result = "";
        for (int i = a.size() - 1, j = b.size() - 1; i >= 0 || j >= 0; --i, --j) {
            int idx = carry;
            if (i < 0) {
                idx += (b[j] - '0');
            } else if (j < 0) {
                idx += (a[i] - '0');
            } else {
                idx += (a[i] - '0') + (b[j] - '0');
            }
            carry = idx / 2;
            idx %= 2;
            result = num[idx] + result;
        }
        if (carry) {
            result = '1' + result;
        }
        return result;
    }

415. Add Strings

Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.

Note:

1. The length of both num1 and num2 is < 5100.

2. Both num1 and num2 contains only digits 0-9.

3. Both num1 and num2 does not contain any leading zero.

4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

S: O(n)

    string addStrings(string num1, string num2) {
        if (num1.size() < num2.size()) return addStrings(num2, num1);
        string result = "";
        int carry = 0;
        int n1 = num1.size(), n2 = num2.size();
        for (int i1 = n1 -1, i2 = n2 - 1; i1 >= 0; --i1, --i2) {
            int a = num1[i1] - '0';
            int b = i2 < 0? 0 : num2[i2] - '0';
            int sum = a + b + carry;
            result = to_string(sum % 10) + result;
            carry = sum / 10;
        }
        if (carry) result = '1' + result;
        return result;
    }