This is a question from Codility.

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 representation1001and contains a binary gap of length 2. The number 529 has binary representation1000010001and contains two binary gaps: one of length 4 and one of length 3. The number 20 has binary representation10100and contains one binary gap of length 1. The number 15 has binary representation1111and has no binary gaps.

Write a function:

int solution(int 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 representation10000010001and so its longest binary gap is of length 5.

Assume that:

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

Complexity:

• expected worst-case time complexity is O(log(N));
• expected worst-case space complexity is O(1).

Solution:

The core of the problem is converting a number into its binary representation and found the maximum number of consecutive zeros bounded by two ones.

1. If you have a function that helps you get the binary representation directly, use it.

2. If you want to go through the conversion process, consider it as a sequence such as 1001, where N is 1, 2, 4, 9 on top of it. So each time you move forward by one step.

Caveats (Probably only works for me):

1. Max type of question, you don't need to remember the previous results unless required. Hence, you can use only one-time pass, use a variable that will reset once a satisfying result ends.

2. When you are checking a state in a while loop, don't change the state.

Code:

int solution(int N) {
// write your code in C++14 \(g++ 6.2.0\)

if \(N < 2\) return 0; 

int max = 0;

int count = 0;

while \(N % 2 == 0\) N = N / 2;



while \(N > 0\) {

    if \(N % 2 == 1\) {

        if \(count > max\) max = count;

        count = 0;

        N = N / 2;

    } else {

        count++;

        N = N / 2;

    }       

}



return max;
}

1. N is the variable to determine when to stop
2. N % 2 determine what to do.
3. max is the invariant record the desired value.