Short Premise

Find the maximum consecutive zeros that are surrounded by ones in the binary representation of a number N in a range between 0 and 2.147.483.647.

Approach

The approach to this solution is to build a state machine that can process the language generated by zeros and ones in a binary number and count the size of all zero gaps. The maximum gap should be computed from all gap values.

Code

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

int binary_gap(int N) {

// store values of maximum and local gap
int maximum_gap = 0;
int local_gap = 0;

// get number of bits in the binary representation of the number N
int nbits = ceil(log(N) / log(2));

// the start index used to store the start point of the current binary gap
int start_idx = 0;

// a simple state machine that process each position of the binary number N
// the complexity of this algorithm is majored by this loop, leading to the
// worst case complexity of O(N).
for(int idx = 0; idx < nbits; idx++) {

switch(N & 3) {

case 0b01:
start_idx = idx+1;
break;

case 0b10:
if (start_idx)
local_gap = idx - start_idx + 1;
if (local_gap > maximum_gap) maximum_gap = local_gap;
start_idx = 0;
break;

}

N = N >> 1;
}

return maximum_gap;
}

int solution(int N)
{
return binary_gap(N);
}

Results

This code has O(N) complexity since the number of computations increases linearly. The evaluation on the website got 100% in all criteria.