67. Add Binary

Add Binary

Problem 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.

Approach) Using Bigint

Below is my boring but clear solution, using the proposed BigInt object.

The idea is to use inputs, a and b to build two binary literals. Calculating the sum is done by calling the BigInt function on our binary literals, adding them together, and returning the sum with a call to the toString method with 2 as the argument, since we are working with binary numbers.

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function(a, b) {
  const aBin = `0b${a}`
  const bBin = `0b${b}`
  const sum = BigInt(aBin) + BigInt(bBin)
  return sum.toString(2)
};

Approach) Using Bigint - Single line

var addBinary = function(a, b) {
    return (BigInt("0b"+a) + BigInt("0b"+b)).toString(2);
}

BigInt is used to represent Integers greater than 2^53 -1.
(2^53) - 1 is the Maximum Number of Primitive which can be safely represented using JavaScript.
This is represented by MAX_SAFE_INTEGER.
We coule use parseInt("number", base) to convert the arguments 'a' and 'b' from binary base to decimal base and then add them together.
But the problem here is, if we have integers, i.e a or b's binary value to be huge (that is if the numbers passed to a or b is really big which is more than 2^52 -1), then javascript can not process it as the max Number primitive it can work with safely is 2^53 -1 or lesser.

Therefore, we make use of BigInt to represent all kind of numbers, small to large Integers.
The BigInt object takes a String Integer literal as argument and then returns us a number which is of theBigInt datatype.

So, here we need to pass the string (which should be an Integer Literal), as whichever base it is currently represented as.
In our case we have 'a' and 'b' as binary numbers(strings).
We need to tell BigInt() that 'a' and 'b' are Binary numbers, so we append '0b' to the beginning of 'a' and 'b' and then pass them to BigInt().
Similarly, if we have Hexadecimal number we prefix '0x' and for Octal numbers we prefix '0o'.

Once we have converted our binary numbers 'a' and 'b' to BigInt datatype, we add them using normal addition (+) operator.

Now, we use the toString method to convert our BigInt number (sum calculated) to String which is a Binary, by passing the base we want to convert our argument to.
str.toString(2) converts the str string to Binary (base 2).

Approach) Brute Force

let addBinary = (a, b) => {
  // Truth Table
  // 1st + 2nd + carry = sum, new carry, decimal sum
  //   0 +  0  + 0 = 0, 0 (0)
  //   0 +  0  + 1 = 1, 0 (1)
  //   0 +  1  + 1 = 0, 1 (2)
  //   1 +  1  + 1 = 1, 1 (3)

  let carry = 0;
  let result = '';

  let len1 = a.length - 1;
  let len2 = b.length - 1;

  for (; len1 >= 0 || len2 >= 0 || carry > 0; len1--, len2--) {
    let sum = (+a[len1] || 0) + (+b[len2] || 0) + carry;
    if (sum > 1) {
      sum = sum % 2;
      carry = 1;
    } else {
      carry = 0;
    }
    result = `${sum}${result}`;
  }
  return result;
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem 67. Add Binary

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!