Leetcode: Add Binary

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

This should be pretty simple. Here are the examples:

Example 1:

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

Output: "100

Example 2:

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

Output: "10101" 

Constraints: 

1 <= a.length, b.length <= 10^4

a and b consist only of '0' or '1' characters.

Each string does not contain leading zeros except for the zero itself.

There are strings. 

class Solution {

    public String addBinary(String a, String b) {

        return Integer.toBinaryString(Integer.parseInt(a, 2) + Integer.parseInt(b, 2));

    }

}

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

However this approach is not great, since we can have overflow (33 for integer, and 65 for long). We need a different approach to this problem. Here is the Python version of this problem. 

class Solution: 

    def addBinary(self, a, b) -> str:

        return '{0:b}'.format(int(a,2) + int(b,2))

And this article has O(M + N) time complexity and 2 drawbacks.

So first, we want to add the binary if the second string is larger than the first string. We want to make a carry variable as well. We want to figure eout the carry, and see if the carry is equal to 1 which is if the number is 1.

class Solution {

    public String addBinary(String a, String b) {

        int n = a.length();

        int m = b.length();

        //reverse if one string is longer than another

        if(n < m) return addBinary(b, a); 

        int L = Math.max(n, m);

        StringBuilder sb = new StringBuilder(); 

        int carry = 0;

        int j = m - 1;

        //traverse through the string

        for(int i = L - 1; i > -1; --i) {

            //add these sums.

            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 is divided by 2 whenever both number equal to one, so the carry will be 1 no matter what on the next iteration.

            carry /= 2;

        }

        //append the 1 if the carry is 1 

        if(carry == 1) sb.append('1');

        //reverse and return the final string 

        sb.reverse();

        return sb.toString();

    }

}

The complexity of this is O(max(N,M)), since this is linear. Now the other method that I want to discuss is the bit manipulation.

So while the carry is nonzero, current answer without carry is x ^  y and current answer is left shifted and x and y is carry = (x & y) << 1 and the job is done and then prepare for the next loop. 

I prefer to do this in Python.

class Solution: 

    def addBinary(self, a, b):

        x,y = int(a, 2), int(b,2)

        # shift bits of the integer, and also xor each integer to each other 

        while y:

            x,y = x ^ y, (x & y) << 1

    # return the integer

        return bin(x)[2:]