Add Binary

Problem Source: LeetCode
Companies: Facebook, Amazon, Apple, Google

Problem Statement :

Given two binary strings return their sum(also a binary string).

The input strings are both non-empty and contains only characters 1 or 0.

Example 1:

Input: a = “1”, b = “100”

Output: “101”

Example 2:

Input: a = “1101”, b = “111”

Output: “10100”

Constraints:

• Each string consists only of '0' or '1' characters.
• 1 <= a.length, b.length <= 10^4
• Each string is either "0" or doesn’t contain any leading zero.

Solution 1:

A simple solution for this problem can be implemented using built-in functions of java or python.

Implementation

Java

class Solution {
  public String addBinary(String a, String b) {
    return Integer.toBinaryString(Integer.parseInt(a, 2) + Integer.parseInt(b, 2));
  }
}

Python

class Solution:
    def addBinary(self, a, b) -> str:
        return '{0:b}'.format(int(a, 2) + int(b, 2))

Above implementation is done in following steps:

1. Convert the given input into integers.
2. Compute the sum.
3. Return the sum back into binary form.

Analysis:

The overall algorithm has O(N+M) time complexity.

There are certain drawbacks:

1. In Java, the above solution is limited to the input strings with small length. For larger length of input strings, the result of conversion into integers will not fit into Integer, Long or BigInteger.

2. For large inputs, this performance is quite low.

Solution 2:

Bit-by-Bit Computation:

Algorithm:

In this approach, we don’t have to convert binary strings into integers and vice versa. Here our computation will be done bit by bit, starting from the lowest bit(LSB). At each step we will compute carry by adding the current bit in it. Take a new string and append the required answer, computed at each step.

We will start from carry = 0 and

If the string a has 1 in its lowest bit -> add 1 to the carry. Move to the string b and check the same and add 1 to the carry if the lowest bit of string b is 1.

Now, we will have the values of carry -> 0 or 1 or 2.

Append the required value to the string. We can get this value by simple calculating carry = carry % 2. Move the next order bit.

Repeat these steps untill all the bits of a and b are used up and then check for the carry, if carry still has a nonzero value then append it to the string.

Reverse the string, which will be equal to the required answer.

Implementation

Java

class Solution {
  public String addBinary(String a, String b) {
    int n = a.length(), m = b.length();
    if (n < m) return addBinary(b, a);
    int L = Math.max(n, m);

    StringBuilder sb = new StringBuilder();
    int carry = 0, j = m - 1;
    for(int i = L - 1; i > -1; --i) {
      if (a.charAt(i) == '1') ++carry;
      if (j > -1 && b.charAt(j--) == '1') ++carry;

      if (carry % 2 == 1) sb.append('1');
      else sb.append('0');

      carry /= 2;
    }
    if (carry == 1) sb.append('1');
    sb.reverse();

    return sb.toString();
  }
}

Python

class Solution:
    def addBinary(self, a, b) -> str:
        n = max(len(a), len(b))
        a, b = a.zfill(n), b.zfill(n)

        carry = 0
        answer = []
        for i in range(n - 1, -1, -1):
            if a[i] == '1':
                carry += 1
            if b[i] == '1':
                carry += 1

            if carry % 2 == 1:
                answer.append('1')
            else:
                answer.append('0')

            carry //= 2

        if carry == 1:
            answer.append('1')
        answer.reverse()

        return ''.join(answer)

Complexity analysis:

• Time complexity: O(max(N,M)), where NN and MM are lengths of the input strings a and b.

• Space complexity: O(max(N,M)) to keep the answer.