67. Add Binary

Time: O(n)

Space: O(n)

Intuition

Add two binary strings digit by digit from right to left, maintaining a carry. The result is built in reverse (or using a StringBuilder prepending at index 0, or reversing at the end).

Algorithm

1Initialise i=a.Length-1, j=b.Length-1, carry=0, StringBuilder sb.
2While i>=0 or j>=0 or carry>0:
3 sum = carry + (i>=0 ? a[i--]-"0" : 0) + (j>=0 ? b[j--]-"0" : 0).
4 Prepend (sum%2) to sb. carry = sum/2.
5Return sb.ToString().

Example Walkthrough

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

1.i=1,j=0: sum=0+1+1=2. append 0, carry=1.
2.i=0,j=-1: sum=1+1+0=2. append 0, carry=1.
3.i=-1,j=-1,carry=1: sum=1. append 1, carry=0.
4.Reversed: "100".

Output: "100"

Common Pitfalls

•Continue the loop while carry>0 even after both strings are exhausted.

67.cs

// Approach: Simulate bit-by-bit addition from LSB backwards with a carry bit,
// then reverse the result.
// Time: O(n) Space: O(n)

public class Solution
{
    public string AddBinary(string a, string b)
    {
        StringBuilder sb = new StringBuilder();
        int carry = 0;
        int i = a.Length - 1;
        int j = b.Length - 1;

        while (i >= 0 || j >= 0 || carry == 1)
        {
            if (i >= 0)
                carry += a[i--] - '0';
            if (j >= 0)
                carry += b[j--] - '0';
            sb.Append(carry % 2);
            carry /= 2;
        }

        var charArray = sb.ToString().ToCharArray();
        Array.Reverse(charArray);
        return new string(charArray);
    }
}

Was this solution helpful?