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"
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:
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
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
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
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
};
github: https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/addBinary.js
Oldest comments (0)