Add Binary

---

Add Binary: 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 <= 10^4
• a and b consist only of '0' or '1' characters.
• Each string does not contain leading zeros except for the zero itself.

---

Try this Problem on your own or check similar problems:

1. Plus One
2. Add to Array-Form of Integer
3. Multiply Strings

Solution:

Java

public String addBinary(String a, String b) {
    StringBuilder sb = new StringBuilder();
    int i = a.length() - 1, j = b.length() - 1;
    int carry = 0;

    while(i >= 0 || j >= 0 || carry > 0){
        int sum = 0;
        if(i >= 0) sum += (a.charAt(i--) - '0');
        if(j >= 0) sum += (b.charAt(j--) - '0');
        sum += carry;

        if(sum == 0 || sum == 1){
            sb.append(sum);
            carry = 0;
        }else{
            sb.append(sum % 2);
            carry = 1;
        }
    }
    sb.reverse();
    return sb.toString();
}

JavaScript

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function (a, b) {
  let sb = "";
  let i = a.length - 1;
  let j = b.length - 1;
  let carry = 0;

  while (i >= 0 || j >= 0 || carry > 0) {
    let sum = 0;
    if (i >= 0) sum += parseInt(a.charAt(i--));
    if (j >= 0) sum += parseInt(b.charAt(j--));
    sum += carry;

    if (sum === 0 || sum === 1) {
      sb += sum;
      carry = 0;
    } else {
      sb += sum % 2;
      carry = 1;
    }
  }
  return sb.split("").reverse().join("");
};

Python

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        sb = []
        i = len(a) - 1
        j = len(b) - 1
        carry = 0

        while i >= 0 or j >= 0 or carry > 0:
            sum = 0
            if i >= 0:
                sum += int(a[i])
                i -= 1
            if j >= 0:
                sum += int(b[j])
                j -= 1
            sum += carry

            if sum == 0 or sum == 1:
                sb.append(str(sum))
                carry = 0
            else:
                sb.append(str(sum % 2))
                carry = 1

        return ''.join(sb[::-1])

C++

class Solution {
public:
    string addBinary(string a, string b) {
        string sb;
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;

        while (i >= 0 || j >= 0 || carry > 0) {
            int sum = 0;
            if (i >= 0)
                sum += (a[i--] - '0');
            if (j >= 0)
                sum += (b[j--] - '0');
            sum += carry;

            if (sum == 0 || sum == 1) {
                sb += to_string(sum);
                carry = 0;
            } else {
                sb += to_string(sum % 2);
                carry = 1;
            }
        }
        reverse(sb.begin(), sb.end());
        return sb;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(max(m, n))
• Space Complexity: O(1)

---

Explanation:

So the first question to the interviewer should be in if we have leading 0 in the number binary representation. Since by the problem statement constraints we don't, we can proceed. We iterate over both input strings, and the time complexity will be proportional to the length of the longer of our two strings. O(max(m,n)). We also do the binary addition like we do the regular addition from the right to left, so we put two pointers at the end of both strings and iterate towards the start. Since we can have 1 as current bit of our first string and 1 as current bit of our second string we also have to define a carry varible to track the carry of summation from the last step. We don't end our loop as long as we have at least one valid pointer (haven't reach the start of a string traversing from end to start) or we have a carry larger than 0. Each iteration we decrement the pointers moving them to the left, and we append the sum of the current step to the StringBuilder following the rules:

• if sum is either 0 or 1 we don't carry anything to the next step so we just set the bit of the result
• if it is larger than 1 it can only be 2 (1+1) or 3 (1+1 and 1 from last operation carry), so we append sum % 2 (for 2 it will be 0 and for 3 it will be 1) and we also carry over 1.

Since we have StringBuilder in reverse order now, we do additional reverse and return it as our final result. As for the space complexity being constant, you could argue that it is also O(max(m,n)), but generally we don't include the space required to save the result which will be returned from the function towards the total complexity.