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:

  1. Initialization: Create an integer carry to store the carry-over bit (initialized to 0). Create a StringBuilder to build the result string. We'll process the strings from right to left (least significant bit to most significant bit).

  2. Iteration: Use a while loop to iterate as long as there are bits to process in either a or b, or as long as there's a carry. Use i and j to keep track of the indices for strings a and b respectively, moving from right to left.

  3. Bitwise Addition: Inside the loop:

    • Get the current bits from a and b (handling cases where one string is longer than the other by considering the bit as '0' if the index is out of bounds). Use int.Parse(bit) to convert the string representation of a bit ('0' or '1') to an integer.
    • Calculate the sum of the bits and the carry: sum = bit_a + bit_b + carry.
    • Update the carry: carry = sum / 2.
    • Append the least significant bit of the sum (sum % 2) to the StringBuilder.

  4. Final Carry: After the loop, if there's a remaining carry ( carry == 1), append it to the StringBuilder.

  5. Reverse: Reverse the StringBuilder to get the correct order of bits (we built the string from right to left).

  6. Return: Return the string representation of the StringBuilder.

Explanation:

The solution simulates binary addition using bitwise operations. The carry variable handles the carry-over from each bit addition. The modulo operator (%) extracts the least significant bit (the result of the addition for that position), while integer division (/) gets the carry-over bit. The StringBuilder is used for efficient string manipulation because string concatenation in a loop can be inefficient.

Code:

using System;
using System.Text;

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

        while (i >= 0 || j >= 0 || carry == 1) {
            int bit_a = (i >= 0) ? int.Parse(a[i].ToString()) : 0;
            int bit_b = (j >= 0) ? int.Parse(b[j].ToString()) : 0;

            int sum = bit_a + bit_b + carry;
            carry = sum / 2;
            sb.Append(sum % 2);

            i--;
            j--;
        }

        return sb.ToString().Reverse().ToArray().ToString();
    }
}

Complexity:

  • Time Complexity: O(max(m, n)), where m and n are the lengths of strings a and b respectively. This is because we iterate through the strings at most once.
  • Space Complexity: O(max(m, n)) in the worst case, due to the StringBuilder which stores the result string. The space used by other variables is constant.