Codility's biggest binary gap [100% score]

Question

Task description A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N.

For example, number 9 has binary representation 1001 and contains a binary gap of length 2. The number 529 has binary representation 1000010001 and contains two binary gaps: one of length 4 and one of length 3. The number 20 has binary representation 10100 and contains one binary gap of length 1. The number 15 has binary representation 1111 and has no binary gaps. The number 32 has binary representation 100000 and has no binary gaps.

Write a function:

function solution(N);

that, given a positive integer N, returns the length of its longest binary gap. The function should return 0 if N doesn't contain a binary gap.

For example, given N = 1041 the function should return 5, because N has binary representation 10000010001 and so its longest binary gap is of length 5. Given N = 32 the function should return 0, because N has binary representation '100000' and thus no binary gaps.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..2,147,483,647].

I don't believe the code itself is bad, but I'm not sure if it's good either.

I had one bug once I tested my solution against the test cases codility provides before submitting the task.

The bug I found was related to this line, and was fixed.

return pos - 1; //since it got out of the loop because powOfTwo was bigger than the decimal representation

I was returning just pos, which is clearly a mistake, since it gets out of the loop when it finds a bigger number than the decimal representation the function's receiving, there must be a way for me to avoid thinking about this kind of stuff.

(I know we can get the binary representation of a number using a js function, I just thought the way I did it was a "bit" 😉 more challenging).

I didn't realize at first that if it went out of the loop in the getHeaviestOnePositionInBinaryRep function was because the power of two was bigger than the decimal representation of the number the function was receiving, so something that could have taken like 40 minutes ended up taking 60 minutes because I couldn't find the bug (actually I thought about it for like a minute when I was first writing the code and decided that I was wrong in considering to return pos-1 -ikr? 'think twice, code once' seems to failed for me here-). If Mr. Robot taught us something is that bugs are very important to us, and we need to learn from them.

Anyways, here is the code: (thanks for stopping by)

const getHeaviestOnePositionInBinaryRep = (decimalRep) => {
    let powOfTwo = 1,
        pos = 0;
    while (powOfTwo <= decimalRep) {
        if (powOfTwo == decimalRep) {
            return pos;
        }
        powOfTwo *= 2;
        pos++;
    }
    return pos - 1; //since it got out of the loop because powOfTwo was bigger than the decimal representation
};

const biggestGap = (decimalRepresentation) => {
    let ones = [];
    while (decimalRepresentation > 0) {
        ones.push(getHeaviestOnePositionInBinaryRep(decimalRepresentation));
        decimalRepresentation -= 2 ** ones[ones.length - 1]; //substract 2 to the power of the heaviest one found
    }
    let biggestGap = 0;
    let secondHeaviestOneFoundTillNow = ones.pop();
    let heaviestOneFoundTillNow;
    while (ones.length > 0) {
        heaviestOneFoundTillNow = ones.pop();
        currentGap =
            heaviestOneFoundTillNow - secondHeaviestOneFoundTillNow - 1;
        biggestGap = biggestGap < currentGap ? currentGap : biggestGap;
        secondHeaviestOneFoundTillNow = heaviestOneFoundTillNow;
    }
    return biggestGap;
};

Answer 1

Avoid unnecessary array creation

The code creates an array of the bit positions of ones in a first pass, to iterate over in a second pass to find the biggest gap. It's not a big deal, since the size of the array is bound by the number of bits (32). But it's unnecessary, because you could as well compute the biggest gap during the first pass, without ever creating an array.

const biggestGap = (n) => {
    if (n == 0) return 0;
    
    // skip 0s until the first 1 from the end
    var work = n;        
    while ((work & 1) == 0) {
        work >>= 1;
    }
    
    // skip the 1
    work >>= 1;

    // start tracking the length of sequences of 0s
    var longest = 0;
    var length = 0;
    
    while (work) {
        if (work & 1) {
            longest = Math.max(longest, length);
            length = 0;
        } else {
            length++;
        }
        work >>= 1;
    }
        
    return longest;
}