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