Codility binary gap solution

Question

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

Answer 1

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!

Answer 2

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.