Codility BinaryGap Solution in C++

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.

comments powered by Disqus