67. Add Binary.md

67. Add Binary

• Difficulty: Easy.
• Related Topics: Math, String.
• Similar Questions: Add Two Numbers, Multiply Strings, Plus One.

Problem

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 = "11", b = "1"
Output: "100"

Example 2:

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

Solution

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function(a, b) {
  var len1 = a.length;
  var len2 = b.length;
  var max = Math.max(len1, len2);
  var res = '';
  var carry = 0;
  var val = 0;
  
  for (var i = 0; i < max; i++) {
    val = Number(a[len1 - 1 - i] || 0) + Number(b[len2 - 1 - i] || 0) + carry;
    carry = Math.floor(val / 2);
    res = (val % 2) + res;
  }
  
  if (carry) res = 1 + res;
  
  return res;
};

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(1).