10
\$\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
\$\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;
               }
           } 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\$
  • \$\begingroup\$ @SuchMuchCode Updated answer with code example. \$\endgroup\$ – Mike Brant Aug 3 '16 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\$ – Such Much Code Aug 4 '16 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\$ – Such Much Code Aug 4 '16 at 9:46
  • \$\begingroup\$ Looks like this solution has the best performance results: fiddle.jshell.net/jaycode/gsmXB/light \$\endgroup\$ – Such Much Code Aug 4 '16 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 '18 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\$
  • \$\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\$ – Such Much Code Aug 3 '16 at 16:51
2
\$\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\$
0
\$\begingroup\$

Here is a solution with \$O(n)\$ complexity and fewer conditions:

function solution(N) {
   let str = Number(N).toString(2);

   var maxGap = 0, currentGap = 0;
   var counterFlag = false;

    for (var i = 0, len = str.length; i < len; i++) {
        if (str[i] == 1) 
            maxGap = Math.max(maxGap, currentGap);
            counterFlag = true; // needed to handle the case with zeros only
            currentGap = 0; 
            continue;
        }

        if (counterFlag) currentGap += 1;
    }

    return maxGap;
}
\$\endgroup\$
  • \$\begingroup\$ Alternative solutions are not reviews. Please add at least a review of the code provided or tell why the original approach is seriously flawed. \$\endgroup\$ – Mast Sep 13 '17 at 16:19
  • \$\begingroup\$ You said that this solution is O(n) — are you implying that that the original code is worse than O(n)? Please explain. \$\endgroup\$ – 200_success Sep 13 '17 at 16:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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