Binary String Addition | Facebook Coding Interview Question & Answer

Key Takeaways

hey everyone so a few days ago i asked some of you guys if you want to see a video about a coding tv question and you basically said yes so here it is this is a question that's been asked at facebook among other companies and the question is this you're given two strings each one representing a binary number for example one zero and one and you need to write a function that adds them together so one zero plus one should be one one just as an example and you need to do it in a way that doesn't convert these strings into numbers and we're going to call this function ba and that condition of not converting them into numbers is kind of silly but that's just the question another example would be this one 101 plus 1 to 1 should be 1 0 1 0. and if you want to try solving this problem by yourself pause the video right here and feel free to use these unit tests that i wrote for this problem i'm going to put a link to that in the description of this video and here's my solution the way i thought about this problem is how would i solve this problem if it was on paper well i would you know write down these two numbers and then i would check the last digits first and then i would go from there you know just check them one by one and try to construct the result that way and so we need to create a new variable whether it's on paper or in your code uh called result let's say and we're gonna start it with an empty string and then we're going to have another variable called carry which is going to keep track of if we have a carry of 1 or not so this is going to be either true or false and then in this particular case we're starting with these two digits and the result is empty right now and then we go to this one the result becomes zero and the carry becomes true and then we can keep going that way the result becomes one because we have carry and we have these two digits there on zero and then we can go to the next digits so this is the basics of my solution and i think one thing to note is that it could potentially complicate things if one string is longer than the other one for example like this and you know there are ways to deal with this case but to simplify our code a little bit i'm going to make sure that b1 is longer or the same length as b2 and if that's not the case we're just gonna swap these two variables okay so let's dive into my solution in python here like i said earlier i wrote a bunch of unit tests for this so we have ba of one and zero one plus zero should be one one plus one should be one zero one one one one should one one one plus one should be one zero zero and so on and currently from my function i'm returning one so some of these tests most of these tests should fail and that's actually true my tests are failing and now i'm gonna write my solution like i said the first thing i want to do is i'm going to make sure that length of b1 is greater than or equal to b2 so if that's not the case b1's length is less than b2's length then i'm going to swap these two variables just like that and then like i said earlier i want to start at the last digit of the last digits of these two numbers and then i want to go to the left one by one just like that and to do that what i'm going to do is i'm going to say 4 i in range of length of b1 so this way with this example i would go from zero to one to two to three so zero one two three and we just need to convert it in a way that that it goes from three to two to one to zero to do that we can just do len b1 so the length of b1 minus 1 minus i and i'm going to call this new variable i1 and we can make sure that this is correct by checking that when i is 0 so when we are starting this for loop length of b1 is 4 and so i1 is going to be 3 which is this one and we can do the same thing with b2 by saying i2 equals length of b2 minus 1 minus i and when b1 is longer than b2 i2 is going to be a negative number at some point but if that's the case we can just ignore it and before this for loop we need to define result and carry carry is going to be false initially and for result i'm going to use a list or an array depending on what language you're using so this is going to keep track of the digits in the result and then we're going to convert it into a string later and then in the for loop what i'm gonna do in each loop is i'm gonna count ones and i'm gonna set it to zero at the beginning so as an example if we're looking at these two strings and when i is zero so when the loop starts we're looking at these two digits this one and this one and we can see that we have two ones and if we have carry we it's sort of like having three ones and you know here the problem is a little bit vague but i think it's okay to do this because we're not converting you know these strings into numbers we're just counting the number of ones here so i'm just going to go with this so after that i'm going to say if the current digit that we're looking at from b1 is one then add one to count once and do the same thing with b2 but here we'll need to say if i2 is less than zero we're going to ignore it so we need to add this condition that says if i2 is greater than or equal to zero and if that digit is one then add one to count one and then if carry is true we're going to add one to count ones as well and then after that depending on the value of count ones we can add a different different digit to result so we're going to do that with if count one's mod two is zero so if count once is even then that means it's either zero or two so in that case we're going to add zero two results and else we're gonna add 1 to the result and then if count once is greater than 1 then the carry should be true so we're going to set carry to true and that's it for the for loop and after the for loop we're going to check if carry is true if carry is true we should append one to the result and right now result is reversed so we need to we we need to reverse it back with result.reverse and then we need to convert it into a string with an empty string.join result and then we can just return that okay so hopefully this is gonna work let's see by running this function and it does i passed all the tests okay so that's it for this video uh sorry it's been a while since my last video but let me know if you have any video requests for the future and i'm gonna clear this and turn this back to the code i had so that you can practice if you want to practice by yourself i'm gonna put this in the description below thank you as always for watching my videos and i'll see you guys in the next one