# Binary Gap

Posted in  Vinay Khatri
Last updated on November 4, 2022

## Problem

Given an integer ‘n’, find the maximum gap between two occurrences of 1. If no or only 1 exists in the binary representation, return 0.

`6`

`1`

#### Explanation

The binary of 6 is ‘110,’ and the maximum gap between two 1s is 1.

## Approach

We create a ‘count’ variable to count the number of 0s. We can check the Least Significant Bit (LSB) of ‘n’ one by one and keep right shifting it. If LSB is 1, we keep the count variable as 0 and update the answer. If it is 0, then keep incrementing the value of the count variable. How right shift operation work: If the given sequence of bits is: ‘0101’, then in the right shifting operation, the MSB will become 0 and all the remaining bits shift right by 1, resulting in ‘0010’

## Complexity Analysis

The time complexity is O(logN)) with no extra space required.

### C++ Programming

```#include <bits/stdc++.h>

using namespace std;

// function to get maximum gap between two 1s
int binaryGap(int N) {
int count = -32, ans = 0;

while (N != 0) {
// if the rightmost bit is 1, update the answer
if ((N & 1) == 1) {
ans = max(ans, count);
count = 0;
}
count++;

// right shift N by 1
N >>= 1;
}
return ans;
}

int main() {
int n = 6;

cout << binaryGap(n);
}```

`1`

### Java Programming

```import java.io.*;

class Solution {
// function to get maximum gap between two 1s
public static int binaryGap(int N) {

int count = -32, ans = 0;

while (N != 0) {

// if the rightmost bit is 1, update the answer
if ((N & 1) == 1) {
ans = Math.max(ans, count);
count = 0;
}

count++;

// right shift N by 1
N >>= 1;

}
return ans;
}

public static void main(String[] args) {

int n = 6;

System.out.println(binaryGap(n));

}
}```

`1`

### Python Programming

```# function to get maximum gap between two 1s
def binaryGap(n):
ans = count = 0

while n > 0:

# if the rightmost bit is 1, update the answer
if n & 1:
ans = max(ans, count)
count = 1

elif count:
count += 1

# right shift N by 1
n >>= 1

return ans

n = 6

print(binaryGap(n))```

`1`