67. Add Binary
1. Description
Given two binary strings a and b, return their sum as a binary string.
2. Example
Example 1
Input: a = “11”, b = “1”
Output: “100”
Example 2
Input: a = “1010”, b = “1011”
Output: “10101”
3. Constraints
- 1 <= a.length, b.length <= 10$^{4}$
- a and b consist only of ‘0’ or ‘1’ characters.
- Each string does not contain leading zeros except for the zero itself.
4. Solutions
Bit Manipulation
m = a.size(), n = b.size()
Time complexity: O(max(m, n))
Space complexity: O(1)
class Solution {
public:
string addBinary(const string &a, const string &b) {
const int m = a.size(), n = b.size();
string result;
result.reserve(max(m, n) + 1);
int carry = 0;
for (int i = m - 1, j = n - 1; i >= 0 || j >= 0; --i, --j) {
int sum = carry + (i >= 0 ? a[i] - '0' : 0) + (j >= 0 ? b[j] - '0' : 0);
carry = sum / 2;
result.push_back('0' + sum % 2);
}
if (carry == 1) {
result.push_back('1');
}
reverse(result.begin(), result.end());
return result;
}
};