67. Add Binary - Detailed Explanation

Problem Statement

You are given two binary strings, a and b. The task is to return their sum—as a binary string.

Key Points:

• The strings contain only the characters '0' and '1'.
• The output should also be a binary string representing the sum of the two binary numbers.

Example 1:

• Input: a = "11", b = "1"
• Output: "100"
• Explanation:
  The binary number "11" (which is 3 in decimal) plus "1" (1 in decimal) equals "100" (4 in decimal).

Example 2:

• Input: a = "1010", b = "1011"
• Output: "10101"
• Explanation:
  "1010" (10 in decimal) plus "1011" (11 in decimal) equals "10101" (21 in decimal).

Hints to Approach the Problem

1. Simulate Binary Addition:
   Think of how you add two numbers by hand. Start from the rightmost digits and move left, adding the corresponding digits along with any carry from the previous addition.

2. Manage the Carry:
   Keep track of the carry (which can be either 0 or 1). At each step, sum the corresponding digits and the carry, then determine the new digit and the updated carry.

3. Handling Different Lengths:
   The two strings might have different lengths. Ensure your approach handles the case where one string runs out of digits before the other.

4. Reversing the Result:
   As you are adding digits from right to left, you will build the result in reverse order. Remember to reverse it at the end.

Approach

Simulation of Binary Addition (Digit-by-Digit)

Idea:

• Start from the end of both strings.
• Use two pointers (one for each string) and a variable to track the carry.
• In a loop, add the digits (if available) and the carry:
  • Convert the current characters to integers.
  • Compute the sum.
  • The new digit to append is sum % 2.
  • The carry is updated to sum // 2.
• Continue until both strings have been processed and any leftover carry is added.
• Reverse the built result to obtain the final answer.

Detailed Steps:

1. Initialize pointers for both strings (starting from the last index) and set carry to 0.
2. While there are digits left in either string or a non-zero carry:
   • Get the current digit from each string (or 0 if the pointer is out of bounds).
   • Compute the sum: current_digit_a + current_digit_b + carry.
   • Append the digit (sum % 2) to the result.
   • Update the carry (sum // 2).
   • Move the pointers one position to the left.
3. Reverse the result (because the digits are generated in reverse order) and return it.

Step-by-Step Walkthrough

Consider the example a = "1010" and b = "1011".

1. Initialization:

   • Pointer i at end of a (index 3), pointer j at end of b (index 3), and carry = 0.
   • Result list is empty.

2. Iteration:

   • Step 1:
     • a[3] = '0' → 0, b[3] = '1' → 1.
     • Sum = 0 + 1 + 0 = 1.
     • New digit = 1, carry = 0.
     • Append "1" to the result.
   • Step 2:
     • Move pointers: i = 2, j = 2.
     • a[2] = '1' → 1, b[2] = '1' → 1.
     • Sum = 1 + 1 + 0 = 2.
     • New digit = 0 (since 2 % 2 = 0), carry = 1 (since 2 // 2 = 1).
     • Append "0" to the result.
   • Step 3:
     • Move pointers: i = 1, j = 1.
     • a[1] = '0' → 0, b[1] = '0' → 0.
     • Sum = 0 + 0 + 1 = 1.
     • New digit = 1, carry = 0.
     • Append "1" to the result.
   • Step 4:
     • Move pointers: i = 0, j = 0.
     • a[0] = '1' → 1, b[0] = '1' → 1.
     • Sum = 1 + 1 + 0 = 2.
     • New digit = 0, carry = 1.
     • Append "0" to the result.
   • Final Step:
     • Both pointers are now out of bounds but carry = 1 remains.
     • Append "1" to the result.

3. Result Building:

   • The result list (in reverse order) is ["1", "0", "1", "0", "1"].
   • Reversing it gives "10101", which is the final answer.

Complexity Analysis

• Time Complexity: O(n)
  where n = max(length of a, length of b). Each digit is processed once.

• Space Complexity: O(n)
  The space is used for storing the resulting string (and the call stack is O(1) extra space in this iterative approach).

Code Implementation

Python Code