12
\$\begingroup\$

Below is the code I implemented to solve the binary gap problem:

Find longest sequence of zeros, bounded by ones, in binary representation of an integer.

However, it seems to be different from the answers out there. Is it because this is a bad approach in terms of performance? I wanted to get some ideas.

function binaryGap(number) {
    let binary = (number >>> 0).toString(2), // convert to binary
        regex = /(?!1)(0+)(?=1)/g; // regex to match zeros between 1s

    let matches = binary.match(regex);

    return matches ? matches.reduce(function(carry, current){
        return carry.length > current.length ? carry : current;
    }).length : 0;
}
\$\endgroup\$

3 Answers 3

6
\$\begingroup\$

The Regex is computationally heavy. I would consider simply iterating through the bits, keeping track of both the highest binary gap and the current binary gap. You could add optimizations such as that proposed by @konijn to bail out of iteration when you reach a point that you can no longer logically find a larger binary gap than your current max value.

That could be as simple as:

The following is updated per comments:

function binaryGap(number) {
    var binary = (number >>> 0).toString(2);
    var maxGap = 0;
    var currentGap = 0;
    var inGap = false;
    var length = binary.length;
    /*
    Fast return if binary string length is less than 3
    and no gap is possible
    */
    if(length < 3) {
        return 0;
    }
    /*
    Start iterating bits.  We start with second character.
    */
    for(var i = 1; i < length; i++) {
        /*
        See if we should continue evaluation based on whether
        we can actually exceed current maxGap number
        */
        if (maxGap >= currentGap + length - i) {
            break;
        }
        if (inGap === false) {
           // we need to check to see if a new gap is started
           if (binary[i-1] === '1' && binary[i] === '0') {
               // we are in a new gap
               currentGap = 1;
               inGap = true;
           }
        } else {
           // we need to see if gap has ended
           if (binary[i] === '1') {
               // gap has ended
               if (currentGap > maxGap) {
                   maxGap = currentGap;
               }
               inGap = false;
           } else {
               // gap has continued
               currentGap++;
           }
        }
    }
    return maxGap;
}

Here is a simple performance test I set up comparing the approaches. Typically, I am seeing the bit iteration method working in about 20-25% of the time that the regex works.

\$\endgroup\$
9
  • \$\begingroup\$ @SuchMuchCode Updated answer with code example. \$\endgroup\$
    – Mike Brant
    Aug 3, 2016 at 18:54
  • \$\begingroup\$ thank you for this! In your example (the jsfiddle link) you were calling for binaryGapRegex in both occasions. I changed the second one to actually call the iteration one and the results are massively different and now it makes more sense. :) \$\endgroup\$ Aug 4, 2016 at 9:34
  • \$\begingroup\$ The only problem in there is that if I do binaryGap(4), it gives me 2, whereas it should give me 0. Binary for 4 is 100, therefore it is not 'closed' by '1' in the end. In case of regex, I was explicitly saying that the gap is from '1' to '1'. Not sure how I can achieve the same thing in iteration. \$\endgroup\$ Aug 4, 2016 at 9:46
  • \$\begingroup\$ Looks like this solution has the best performance results: fiddle.jshell.net/jaycode/gsmXB/light \$\endgroup\$ Aug 4, 2016 at 10:00
  • 1
    \$\begingroup\$ Your binaryGap(0b10101) returns 2, which is wrong. The original code being reviewed returns 1, which is correct. \$\endgroup\$
    – ppseprus
    Feb 2, 2018 at 0:10
4
\$\begingroup\$

I think your code is okay, however it foregoes some possible optimizations.

Notice that the length of the binary number is only up to 31 bits.

Once your current largest gap found is greater than the number of bits left to analyze, you can stop analyzing. However, match(regex) will always keep on going on with the analysis.

Finally, for the last part, if I did go with a regex, I would have used:

return matches ? matches.sort().pop() : 0;

Post Scriptum, from the site you know that:

N is an integer within the range [1..2,147,483,647].

and, (2147483647).toString(2) equates to "1111111111111111111111111111111" which consists of 31 ones according to (2147483647).toString(2).length Evaluating 31 bits (worst case of the worst case) should always be faster than compiling and matching a regex.

\$\endgroup\$
1
  • \$\begingroup\$ I don't quite understand the 31 bit part. Would you mind dropping a few links I could read up on please? I tried to search for some articles to explain this, but can't find anything useful. Actually, I'm not sure what I should look for. \$\endgroup\$ Aug 3, 2016 at 16:51
3
\$\begingroup\$

To those interested in the complete answer, ES-6 style, airBnB-linter valid, see the code below:

function solution(N) {
  const num = parseInt(N);
  const bin = num.toString(2, 10);
  const arr = bin.split(/(?!1)(0+)(?=1)/);
  const filteredArr = arr.filter(zeroes => zeroes.indexOf('1') === -1) || [];
  const arrSizes = filteredArr.length > 0 ? filteredArr.map(binString => binString.length) : [];
  const max = arrSizes.length > 0 ? arrSizes.reduce((a, b) => a >= b ? a : b) : 0;

  return max;
}
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.