6
\$\begingroup\$

This is how I solved the binary gap problem: Find longest sequence of zeros, bounded by ones, in binary representation of an integer

I wonder how does it fare against solutions such as ones appeared here? Codility binary gap solution using regex

function solution(N) {
    const bin = N.toString(2);

    let currentGap = 0;
    let gaps = [];

    for (i=0; i<bin.length; i++){

      if (bin[i]==="0"){
        currentGap++;

        if (bin[i+1]==="1"){
          gaps.push(currentGap);
          currentGap = 0;
        }
      }
    }

    if (gaps.length===1){
      return gaps[0];
    } else if (gaps.length>1){
      return Math.max(...gaps)
    } else {
      return 0
    }
}
\$\endgroup\$

2 Answers 2

Reset to default
3
\$\begingroup\$

Here's my approach:

function solution(n) { 
    var maxZeros = 0; 
    while(n !== 0 && n % 2 === 0) {
        n >>>= 1;
    }
    for(var curr=0; n !== 0; n>>>=1) { 
        if(n % 2 === 0) { 
            curr++; 
        } else { 
            curr = 0; 
        } 
        maxZeros = Math.max(maxZeros, curr); 
    } 
    return maxZeros; 
}

Some notable differences from your solution:

  • Number isn't converted to binary string. This is half for optimization purposes and half for lack of necessity.
  • Approach to handling the "zero gap must be bound by 1s" requisite. The first 1 is automatically handled because it wouldn't be zero if there were still a 1 to handle. However the lower 1 bound is simply handled by shifting until the first 1 is in the lowest digit, eliminating the need to add flags or extra handling.
  • Notice that no memory is required to hold gap information. It is irrelevant as you can save only the information required as you move along.
  • Value n is checked against being 0 as opposed to being greater than zero just because a negative number should not be disregarded just because it is negative.

Hope that helps! If you have any questions, just ask!

\$\endgroup\$
4
  • \$\begingroup\$ Isn't that O(log n)? \$\endgroup\$ Commented Jun 6, 2017 at 12:38
  • \$\begingroup\$ @Kruga You're right, and OP's would be O(n log n). Nicely spotted. \$\endgroup\$ Commented Jun 6, 2017 at 12:39
  • \$\begingroup\$ What am I saying? OP wasn't calling Math.max inside the loop. That just makes both O(log n). My bad. Removing. \$\endgroup\$ Commented Jun 6, 2017 at 12:42
  • \$\begingroup\$ Hi Neil, interesting solution there! I'll surely inspect it later for actual performance differences using codility out of curiosity. \$\endgroup\$ Commented Jun 7, 2017 at 19:30
1
\$\begingroup\$

You have one bug in your code. The binaryGap function is supposed to be side-effect free. Your implementation isn't since it modifies the global variable i.

To fix this, apply the following patch:

-   for (i=0; i<bin.length; i++){
+   for (let i=0; i<bin.length; i++){

There are 2 lines in your code that are redundant:

if (gaps.length===1){
  return gaps[0];
else

When you remove the above code, you have reduced your code by 2 lines, and it still works the same as before.

The rest of the code looks fine. There's a more efficient way to calculate the binary gap though, as I outlined in my answer to the same question in Java.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.