# 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.