DEV Community

Akhil
Akhil

Posted on

Add Binary, solving Facebook interview question

Question: 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 :

Input: a = "11", b = "1"
Output: "100"
Enter fullscreen mode Exit fullscreen mode

My initial thought was to convert the given string into their respective equivalent decimal forms, add them convert the resultant decimal sum to binary but it seemed too simple since javascript already has an inbuilt function to convert binary to integer and vice-versa. So there's a high probability of interviewer asking to achieve the same without using the inbuilt functions.

I know it sucks but it's what it is : /

Bit Manipulation

Following are rules for adding bits:
Alt Text

So as we can see, we really care about the outcome of sum of two bits

Outcomes

1 > Addition of two bit's results in three possible binary outcomes

1 + 1 = 2
0 + 0 = 0
1 + 0 = 1
0 + 1 = 1
Enter fullscreen mode Exit fullscreen mode

2 > This gives us an opportunity to do something with it:

When we're adding to bits, let's maintain two containers 
sum = 0
carry = 0

0 + 0 = 0 => 0 bit representation so sum = 0 carry = 0
1 + 0 = 1 => 1 bit representation so sum = 1 carry = 0
0 + 1 = 1 => 1 bit representation so sum = 1 carry = 0
1 + 1 = 2 => 10 bit representation so sum = 0 carry = 1

Enter fullscreen mode Exit fullscreen mode

Now our next aim is to convert 2 to 10 or make sum = 0 and carry = 1. We cam achieve this by following :

let sum = 2;
carry = sum / 2   ie 2/2 = 1
sum = sum % 2   ie 2%2 = 0
Enter fullscreen mode Exit fullscreen mode

Now that we have all our bit's and pieces, let's put it all together

var addBinary = function(a, b) {
    a = a.split("").reverse().join("");                  //split and reverse the strings to make out lives a bit easier
    b = b.split("").reverse().join("");
    len = a.length > b.length ? a.length : b.length;    // find larger of two lengths
    result = [];                                        // store results 
    for(let i = 0; i < len; i += 1){
        num1 = Number(a[i] || 0);                       // check if the index exisits
        num2 = Number(b[i]) || 0;
        curr = Number(result[i]||0) + num1 + num2       // add them
        if(curr >= 2){                                  // check if sum > 2
            result[i] = curr%2;                         // perform operations
            result.push(1)
        }
        else{
            result[i] = curr
        }
    }
    return result.reverse().join("")                   //reverse and join for final result
};
Enter fullscreen mode Exit fullscreen mode

github: https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/addBinary.js

Discussion (0)