Add Binary

Leet Code Link - https://leetcode.com/problems/add-binary/description/

Complexity - Easy

Description

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"

#### Constraints:

1 <= a.length, b.length <= 104 a and b consist only of '0' or '1' characters. Each string does not contain leading zeros except for the zero itself.

## Solution
There is a simple way to use built-in functions:

Convert a and b into integers.

Compute the sum.

Convert the sum back into binary form.

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

The overall algorithm has O(N+M) time complexity and has two drawbacks that could be used against you during the interview.

In Java, this approach is limited by the length of the input strings a and b. Once the string is long enough, the result of conversion into integers will not fit into Integer, Long, or BigInteger: 33 1-bits - and b doesn't fit into Integer.

65 1-bits - and b doesn't fit into Long.

500000001 1-bits - and b doesn't fit into BigInteger.

To fix the issue, one could use a standard Bit-by-Bit Computation approach which is suitable for quite long input strings.

Let's consider the numbers bit by bit starting from the lowest one and compute the carry this bit will add.

Start from carry = 0. If a number a has 1-bit in this lowest bit, add 1 to the carry. The same is true for number b: if number b has 1-bit in the lowest bit, add 1 to the carry. At this point, the carry for the lowest bit could be equal to (00) 2 ​ , (01) 2 ​ , or (10) 2 ​ .

Now append the lowest bit of the carry to the answer, and move the highest bit of the carry to the next order bit.

Repeat the same steps again, and again, till all bits in a and b are used up. If there is still nonzero carry to add, add it. Now reverse the answer string and the job is done.

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

        int carry =0 ; int j=n-1;
        StringBuilder sb = new StringBuilder();
        for(int i = m-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();

    }
}

Complexity

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

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

We can also use BigInteger for this purpose where we can use xor operation and operation with shiftleft

import java.math.BigInteger;

class Solution {
    public String addBinary(String a, String b) {
        BigInteger x = new BigInteger(a, 2);
        BigInteger y = new BigInteger(b, 2);
        BigInteger zero = new BigInteger("0", 2);
        BigInteger carry, answer;
        while (y.compareTo(zero) != 0) {
            answer = x.xor(y);
            carry = x.and(y).shiftLeft(1);
            x = answer;
            y = carry;
        }
        return x.toString(2);
    }
}

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

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