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();
int i = m - 1, j = n - 1, k = max(m, n), carry = 0;
string sum(k + 1, '0');
while (i >= 0 || j >= 0) {
int digit = carry;
if (i >= 0) {
digit += a[i--] - '0';
}
if (j >= 0) {
digit += b[j--] - '0';
}
sum[k--] += digit & 1;
carry = digit >> 1;
}
if (carry == 1) {
sum.front() = '1';
} else {
sum.erase(sum.begin());
}
return sum;
}
};