Codility binary gap solution using regex

Question

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;
}

Answer 1

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.

Answer 2

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.

Answer 3

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;
}