# Codility binary gap solution

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


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!

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

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.