Solution: Add Binary

The idea is to add binary numbers bit by bit while keeping track of any carry that occurs during the process. We iterate through both input strings in reverse order, calculate the sum and carry for each bit, update the result, and finally handle any remaining carry. The result is a valid binary sum of the two input binary strings.

Here are the steps of the algorithm:

1. Initialize two variables:

   • result: This list will store the binary sum in reverse order.
   • carry: This variable will keep track of any carry that occurs during the addition process and is initialized with $0$.

2. Initialize two pointers to traverse the binary strings in reverse order:

   • ptr1: This pointer will traverse str1.

   • ptr2: This pointer will traverse str2.

3. Traverse the strings in reverse order using the above pointers:

   • Extract the binary digits at the current position of ptr1 and ptr2. If either pointer goes beyond the string’s length, $0$ is used for that string.

   • Calculate the sum, total_sum, of the current digits along with carry from the previous step.

   • The current_digit is computed as remainder of total_sum when divided by $2$, representing the current bit value.

   • carry for the next iteration is updated by dividing total_sum by $2$.

   • current_digit is appended to result.

   • Both ptr1 and ptr2 are moved one position to the left.

4. Repeat step $3$ until the strings are completely traversed.

5. If there is still a carry left i.e, carry = 1, it’s appended to result.

6. result contains binary sum in reverse order. It is reversed, converted to string, and returned.

Let’s look at the following illustration to get a better understanding of the solution:

Let’s implement the algorithm as discussed above: