Binary Gap

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.

Sample Input

6

Sample Output

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);
}

Output

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));

  }
}

Output

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))

Output

1

People are also reading:

• Monotonic Array
• Arranging Coins
• Maximum Units
• Missing Numbers
• Mountain Array
• What is Pseudocode?
• Dropping Point of an Egg
• Smallest Subtree with All Deepest Nodes
• Find the closest pair from two arrays
• Count Inversions