3
\$\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\$
1
\$\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\$
  • \$\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

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.