Add Binary

Given two binary strings, return their sum as a binary string. Converting to integers directly can overflow for long inputs, so you must add digit-by-digit.

Function signature

func AddBinary(a, b string) string

Inputs / outputs

• a, b: binary strings (most significant bit first).
• Return: binary sum string.

Example

a = "1010", b = "1011"
Process from right:
0+1=1 (carry 0)
1+1=0 (carry 1)
0+0+1=1
1+1=0 (carry 1)
Final carry 1
Output: "10101"

Constraints

• 1 <= len(a), len(b) <= 10_000
• Strings contain only '0' and '1'

Core idea (near-solution)

Simulate binary addition from right to left with a carry.

Invariant: after processing suffixes a[i+1:] and b[j+1:], carry is the correct carry-out for that suffix.

Algorithm (step-by-step)

1. Set indices i=len(a)-1, j=len(b)-1, carry=0.
2. While i>=0 or j>=0 or carry>0:
   • Sum current bits plus carry.
   • Append sum % 2 to result.
   • Update carry = sum / 2.
   • Move indices left.
3. Reverse the result bytes and return as string.

Correctness sketch

• Invariant: after processing suffixes a[i+1:] and b[j+1:], carry is the correct carry-out for that suffix.
• Bitwise operations preserve the required per-bit invariant.
• Combining results across bits reconstructs the correct value.
• Therefore the final bit-accumulated result is correct.

Trace (hand walkthrough)

Example input:
a = "1010", b = "1011"
Process from right:
0+1=1 (carry 0)
1+1=0 (carry 1)
0+0+1=1
1+1=0 (carry 1)
Final carry 1
Output: "10101"

Walk:
- from right: 0+1=1 (carry 0)
- 1+1=0 (carry 1)
- 0+0+1=1 (carry 0)
- 1+1=0 (carry 1), final carry 1 -> 10101

Pitfalls to avoid

• Forgetting to append the final carry.
• Building the result left-to-right without reversing.
• Mishandling different lengths.

Complexity

• Time: O(n)
• Extra space: O(n) for the output.

Implementation notes (Go)

• Build into a []byte and reverse at the end for efficiency.
• Use byte('0'+bit) when appending digits.