Grind 75 Question 21: Add Binary

Time for a long-overdue primer on binary.

The Problem

Given two binary strings a and b, return their sum as a binary string.

The Initial Attempts

The problem? The problem is, I know nothing about binary. Adding binary? That’s a big old nope from me.

Still. I decide to teach myself, and turn to a Wikihow article to educate myself on how to translate binary into our standard base-ten digits (it’s not too bad, honestly). I don’t even bother whiteboarding my initial code; it takes a few tries before addedDigit returns the proper number, mostly because I’m a doofus.

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function(a, b) {
    
    function binaryToDigit(a){
        let digit = 0;
        for(i = a.length -1; i >= 0; i--){
            digit += a[i] * (Math.pow(2, i))
        }
        return digit;
    }
    
    const addedDigit = binaryToDigit(a) + binaryToDigit(b)
    return addedDigit;

};

And now to solve the last part of the problem, which is turning it back into binary…

I get this far:

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function(a, b) {
    
    function binaryToDigit(num){
        let digit = 0;
        let j = 0;
        for(i = num.length -1; i >= 0; i--){
            digit += (num[j] * (Math.pow(2, i)))
            j++
        }
        return digit;
    }
    
    let addedDigit = binaryToDigit(a) + binaryToDigit(b)
    const binaryTotal = []
    
    if (addedDigit == 0) binaryTotal.push(0);
    
    while(addedDigit > 0){
        if(addedDigit%2 == 1){
            binaryTotal.splice(0, 0, 1);
            addedDigit = (addedDigit-1)/2
        } else {
            binaryTotal.splice(0, 0, 0)
            addedDigit = addedDigit/2
        }
    }
    return binaryTotal.join('')
};

Test cases pass. I submit. It throws the most ridiculous test case at me and that’s when I break. I can’t do it. I don’t even know where to begin to fix this train. It’s time to turn to Neetcode to see what I’m doing wrong.

The Solution

Soooo it turns out I was overcomplicating the question. This is literally a matter of adding and carrying, except using ones and zeros instead of all the digits. Derp. Using Neetcode’s solution as a guide, here is the answer I came up with:

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function(a, b) {
    const added = [];
    const aArray = a.split('');
    const bArray = b.split('');
    let carry = 0;
    
    aArray.reverse();
    bArray.reverse();
    for(i = 0; i < Math.max(aArray.length, bArray.length); i++){
        let digitOne = 0;
        let digitTwo = 0;
        
        if(i < aArray.length) digitOne = Number(aArray[i]);
        if(i < bArray.length) digitTwo = Number(bArray[i]);
        
        let total = digitOne + digitTwo + carry;
        let remainder = total % 2;
        
        added.push(remainder);
        carry = Math.floor(total/2)
    }
    
    if (carry == 1) added.push(1);
    
    return added.reverse().join('')
};

What it’s doing:

1. Declaring a bunch o’ variables from the start. Added is the array we’re adding the numbers into, which will eventually be reversed, joined back into a string, and returned as the answer. aArray and bArray are the split strings, since you can’t just reverse a string in Javascript. (Yet another reason for me to be swayed towards Python. It’s so sleek!) Carry is self-explanatory, I think. It’s started off at zero, but will get a one as needed. Next, we reverse each of the string arrays (since we start at the end of the numbers in arithmetic and work our way left) and start our for loop.
2. For the longer of the two arrays:
   1. Digit one and digit two are initially declared as zero. This is so nothing funky happens if one array is shorter than the other.
   2. If one or the other array isn’t out of range yet, the symbol at the i is converted to a number and put into its respective digit.
   3. The total is added — both digits, plus the carry as needed.
   4. The remainder is calculated — the number that’s left over when you divide total by two — so that if a carry of one (and it will always be one, never higher) is added to one and one, the remainder number being pushed into the array-to-become-string is a one.
   5. Remainder is pushed into the array-to-become-string!
   6. Carry is updated as the number that we get when we round down from dividing total by two. This somehow works, I suppose because there will never be a total higher than three.
3. Once the for loop is finished, we check that there’s not a leftover carry — if there is, we push it into added and then reverse added before turning it back into a string and returning it. Done!

What I Learned

1. Binary, man.
2. Keep! It! Simple!
3. The bit about the i loop executing for the longer of the arrays is a nice thing to keep tucked away for the future.

Related Posts

F

Five Things for May 10

A

April Recap, May Intentions

F

Five Things for April 26