Name: Add Binary
Difficulty: Easy
Description: Given two binary strings a and b, return their sum as a binary string.
Example:
Input: a = "1010", b = "1011" Output: "10101"
This one stretched the memory. We add bits from right to left, bit by bit, so the first thing we need to do is reverse the string so we can proceed from left to right. Looping through the string, we convert the ascii 1 or 0 to a number and add them, plus our carry. We then calculate the new carry. We use modulas to determine if the total is 3 or 2, in which case our value is 1, else it is 0. Our value is added to our string, but we prefix to output in the correct order.
string addBinary(string a, string b) {
string result = "";
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
int n = max(a.length(), b.length());
int carry = 0;
for (int i = 0; i < n; ++i) {
int x = i < a.length() ? a[i] - 48 : 0;
int y = i < b.length() ? b[i] - 48 : 0;
int total = x + y + carry;
carry = total / 2;
result = to_string(total % 2) + result;
}
return carry == 0 ? result : "1" + result;
}