5
\$\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\$
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!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Isn't that O(log n)? \$\endgroup\$ – Kruga Jun 6 '17 at 12:38
  • \$\begingroup\$ @Kruga You're right, and OP's would be O(n log n). Nicely spotted. \$\endgroup\$ – Neil Jun 6 '17 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\$ – Neil Jun 6 '17 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\$ – kdenz Jun 7 '17 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.

| improve this answer | |
\$\endgroup\$

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