Binary Gap

Posted in

Binary Gap
vinaykhatri

Vinay Khatri
Last updated on March 29, 2024

    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:

    Leave a Comment on this Post

    0 Comments