Add Binary easy

Problem Statement

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

Example 1:

Input: a = "11", b = "1" Output: "100"

Example 2:

Input: a = "1010", b = "1011" Output: "10101"

Steps to Solve

1. Initialization: We'll use two pointers, i and j, to iterate through strings a and b from the end (least significant bit). We'll also initialize a carry variable carry to 0. We'll build the result string from right to left.

2. Iteration: We iterate while either i or j is within the bounds of their respective strings, or while carry is 1 (handling any remaining carry).

3. Bitwise Addition: In each iteration, we extract the bits from a and b (or 0 if the pointer is out of bounds). We add these bits along with the carry. The sum modulo 2 gives us the current bit to append to the result, and the integer division by 2 gives us the new carry.

4. Result Building: We convert the current bit (0 or 1) to a character ('0' or '1') and prepend it to the result string.

5. Return: After the loop, we return the final result string.

Explanation

The algorithm simulates binary addition using bitwise operations. The modulo 2 operation (% 2) gives us the remainder (the least significant bit of the sum), and the integer division by 2 (/ 2) gives us the carry (the most significant bit of the sum). Working from right to left allows us to correctly handle the carry propagation.

Code

#include <string>
#include <algorithm>

using namespace std;

string addBinary(string a, string b) {
    string result = "";
    int i = a.length() - 1;
    int j = b.length() - 1;
    int carry = 0;

    while (i >= 0 || j >= 0 || carry) {
        int sum = carry;
        if (i >= 0) sum += a[i--] - '0'; // Convert char to int
        if (j >= 0) sum += b[j--] - '0';
        result = to_string(sum % 2) + result; //Prepend the bit to the result
        carry = sum / 2;
    }

    return result;
}

Complexity Analysis

• Time Complexity: O(max(m, n)), where m and n are the lengths of strings a and b. This is because we iterate through the strings at most once.

• Space Complexity: O(max(m, n)), in the worst case, the length of the result string can be at most max(m, n) + 1 (to account for an extra carry). The space used by the result string dominates the space complexity.