Problem

Given two binary strings a and b, return their sum as a binary string.

Examples

Example 1:

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

Example 2:

Input: a = "1010", b = "1011"
Output: "10101"

Solution

Method 1 - Start From End and Take the Carry

Here is the approach:

  1. Initialize a StringBuilder:

    • Use a StringBuilder to construct the result string.

  2. Initialize Pointers and Carry:

    • Use two pointers i and j to traverse the binary strings from the end towards the beginning.
    • Use a variable carry to keep track of the carry-over during the addition process.

  3. Digit-by-Digit Addition:

    • Iterate through both strings from the end to the beginning.
    • Add corresponding digits from both strings along with the carry.
    • Append the result of the addition modulo 2 (i.e., the sum’s last binary digit) to the StringBuilder.
    • Update the carry to be the integer division of the sum by 2.

  4. Handle Remaining Carry:

    • After exiting the loop, check if there is any remaining carry and append it to the result.

  5. Reverse the StringBuilder:

    • Since the result is constructed in reverse order, reverse the StringBuilder at the end to get the correct binary sum.

Very simple, nothing special. Note how to convert a character to an int. Two pointers starting from the back, just think of adding two regular ints from you add from back

Code

Java
public class Solution {
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int i = a.length() - 1, j = b.length() - 1, carry = 0;
        
        while (i >= 0 || j >= 0) {
            int sum = carry;
            if (i >= 0) {
                sum += a.charAt(i--) - '0';
            }
            if (j >= 0) {
                sum += b.charAt(j--) - '0';
            }
            sb.append(sum % 2);
            carry = sum / 2;
        }
        
        if (carry != 0) {
            sb.append(carry);
        }
        
        return sb.reverse().toString();
    }
}
Python
class Solution:
    def addBinary(self, a: str, b: str) -> str:
        i, j = len(a) - 1, len(b) - 1
        carry = 0
        result = []
        
        while i >= 0 or j >= 0:
            sum = carry
            if i >= 0:
                sum += int(a[i])
                i -= 1
            if j >= 0:
                sum += int(b[j])
                j -= 1
            result.append(str(sum % 2))
            carry = sum // 2
        
        if carry:
            result.append(str(carry))
        
        return ''.join(result[::-1])

Complexity

  • ⏰ Time complexity: O(max(m, n)), where m and n are the lengths of the binary strings a and b. The algorithm processes each digit of the longer string once.
  • 🧺 Space complexity: O(max(m, n)) for storing the output in the StringBuilder.

Method 2 - Use Xor for Digit and Mod for Carry

To add two binary strings a and b, the approach involves simulating the digit-by-digit addition process from the least significant digit to the most significant digit, similar to manual binary addition.

Here is the approach:

  1. Handle Null or Empty Strings:
    • If either string a or b is null or empty, return the other string as the result.
  2. Convert Strings to Character Arrays:
    • Convert the binary strings a and b to character arrays for easy manipulation.
  3. Initialization:
    • Initialize pointers i and j to point to the last characters of the arrays aArray and bArray.
    • Initialize variables aByte, bByte, carry, and result for the addition process.
  4. Digit-by-Digit Addition:
    • Use a while loop to iterate through both arrays from the end to the beginning and perform binary addition.
    • Use bitwise XOR to calculate the sum of the current digits and the carry.
    • Update the carry for the next iteration based on the sum of the current digits.
    • Append the result of the current addition to the StringBuilder.
  5. Reverse and Return:
    • Reverse the StringBuilder to obtain the correct order of the resultant binary string.
    • Return the resultant string.

Code

Java
public class Solution {
    public String addBinary(String a, String b) {
        if (a == null || a.isEmpty()) {
            return b;
        }
        if (b == null || b.isEmpty()) {
            return a;
        }

        char[] aArray = a.toCharArray();
        char[] bArray = b.toCharArray();
        StringBuilder stb = new StringBuilder();

        int i = aArray.length - 1;
        int j = bArray.length - 1;
        int carry = 0;

        while (i >= 0 || j >= 0 || carry == 1) {
            int aByte = (i >= 0) ? aArray[i--] - '0' : 0;
            int bByte = (j >= 0) ? bArray[j--] - '0' : 0;
            int result = aByte ^ bByte ^ carry;
            carry = ((aByte + bByte + carry) >= 2) ? 1 : 0;
            stb.append(result);
        }
        
        return stb.reverse().toString();
    }
}
Python
class Solution:
    def addBinary(self, a: str, b: str) -> str:
        if not a:
            return b
        if not b:
            return a

        aArray = list(a)
        bArray = list(b)
        stb = []

        i, j = len(aArray) - 1, len(bArray) - 1
        carry = 0

        while i >= 0 or j >= 0 or carry == 1:
            aByte = int(aArray[i]) if i >= 0 else 0
            bByte = int(bArray[j]) if j >= 0 else 0
            i, j = i - 1, j - 1
            result = aByte ^ bByte ^ carry
            carry = (aByte + bByte + carry) // 2
            stb.append(str(result))

        return ''.join(reversed(stb))

Complexity

  • ⏰ Time complexity: O(max(m, n)), where m and n are the lengths of the binary strings a and b. This is because we process each digit of the longer string once.
  • 🧺 Space complexity: O(max(m, n)) for storing the output in the StringBuilder.