JavaScript function to convert decimal number to binary

Question

I was recently asked this in an interview for a front-end position and I came up with something like the code below, which seems to work but is clunky. (Number.toString() was not allowed.)

function convertBinary(number) {
  var n = 0;
  var binaryArr = [];

  var difference = Math.pow(2, n);

  //find out how many digits are needed
  while (difference <= number){
    n++;
    difference = Math.pow(2, n);
    binaryArr.push(0);
  }

  n--;

  while(number > 0) {
    if (Math.pow(2, n) <= number) {
      binaryArr[n] = 1;
      number-= Math.pow(2, n);
    }
    n--;
  }

  return binaryArr.reverse().join("") * 1
}

Also I was asked what the Big(o) of this was but had a hard time figuring it out— what is the time complexity of JavaScript reverse?

Answer 1

Strictly speaking, the number parameter isn't decimal; it's just an abstract number. (This is more a criticism of the terminology in your question title than of your code.) On the other hand, it is very weird that you coerce the result into a number (101010) rather than returning it as a string ('101010').

The implementation strategy, using Math.pow(…, 2), strikes me as extravagant. You should be able to do this more efficiently using just arithmetic:

function convertBinary(number) {
    var binaryArr = [];
    for (; number; number /= 2) {
        binaryArr.push(number % 2);
    }
    return binaryArr.reverse().join('');
}

… or the same thing using bitwise operations:

function convertBinary(number) {
    var binaryArr = [];
    for (; number; number >>= 1) {
        binaryArr.push(number & 1);
    }
    return binaryArr.reverse().join('');
}

Answer 2

Also I was asked what the Big(o) of this was but had a hard time figuring it out— what is the time complexity of JavaScript reverse?

Now, I don't know much about Big O notation, but I'll give you my two cents about this issue.

First off, I don't think that the reverse() is actually part of the complexity. Considering this is a built-in function and all you do is simply call it, it can be considered \$O(1)\$.

However, again, I don't think that is actually part of the time complexity; when the interviewer asked that, he/she was most likely referring to your algorithm.

To find the complexity of your algorithm, think of it like this: this function you have written is a function of number; in Big O terms, number would be your n.

Now, basically, all you need to do is find how many "iterations" (not the real thing, but works in this case) your function does based on it's input. To find that, you need to look here:

while (difference <= number){

and here:

while(number > 0) {

Both of these loops involve the only argument number(n) and will run a certain amount of times based on this argument. Looking at these they both run the range of

0 to number, only on powers of 2 in this range.

For example, if number was 5000, then these would be the numbers, then you traverse:

1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096

both times (the first loop you go left to right, the second one you go right to left).

If you look further into this, you might be able to find a proper Big O notation to represent this.

---

Power (look-up) Table!

Looking over your algorithm, I see that you are using Math.pow a lot. While this is a nice method and it is helpful, it can be very inefficient (especially if used too many times).

Focusing only on n, your algorithm does this:

1. Set n to 0
2. Increment n to a limit, calculating Math.pow each increment.
3. Decrement n back down to zero, calculating Math.pow twice for each decrement (except for the first).

So, if the limit ends up being 10 in this case, you would have called Math.pow 28 times.

A way to speed this up would be to create an array and store all the Math.pows in it when you are first incrementing up to the limit. Then, when you are decrementing, simply reference the table for the value. This would reduce those 28 calls down to only 10.

In your first loop:

  while (difference <= number){
    n++;
    powArr[n] = difference = Math.pow(2, n);
    binaryArr.push(0);
  }

Then, in your second loop:

  while(number > 0) {
    var pow = powArray[n];
    if (pow <= number) {
      binaryArr[n] = 1;
      number -= pow
    }
    n--;
  }

Note: I added in a pow variable so you don't have to access the array twice.

Now, your code doesn't have to call this expensive Math.pow as often, overall increasing the speed of your code.

---