CPP: Binary Gap

Solution for the Binary Gap problem in Cpp

Problem Description

Given a positive integer N, examine its binary representation and determine the length of the longest sequence of consecutive zeros that is enclosed by ones on both sides.

A sequence of zeros is considered a valid gap only if it is preceded and followed by a 1 bit.

Any zeros that appear before the first 1 or after the last 1 are ignored.

The goal is to return the maximum length of such a binary gap.

If no valid gap exists, return 0.

Input : N = 9, binary = 1001 and the output = 2

Input: N = 529, binary = 1000010001, and the output = 4

Notes

  • Input N is a positive integer
  • The solution should efficiently analyze bits rather than rely on string conversion
  • Expected time complexity: O(log N)

Solution

cpp 
// you can use includes, for example:
// #include <algorithm>
// #include <iostream>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(int N) {
    // Implement your solution here
    
    // There are 2 steps 
    // 1. converting the number into binary.
    // 2. count after the first 1 the number of zeros 
        // return 0 for no gaps,
        // return the gab

    // to return 0 if no gabs
    int max_gab = 0;
    int current_gab = 0;
    bool is_counting = false;

    // N is from 1 to ... (it is always positive)
    for (; N > 0; N >>= 1){
        // std::cout << (N & 1);
        // start the gab with first one and then count the zeros,
        // and reset every second one.
        if (N & 1) {
            // it could be the end of the gab and the start of the second one.
            // check the second one.
            if (is_counting){
                if (current_gab > max_gab) max_gab = current_gab;
                current_gab = 0;
            } else{
                // pass the first one
                is_counting = true;
            }
        } else if (is_counting) {
            current_gab ++;
        }
    }
    return max_gab;
}