Maximum 0’s between two immediate 1’s in binary representation
Given a number n, the task is to find the maximum 0’s between two immediate 1’s in binary representation of given n. Return -1 if binary representation contains less than two 1’s.
Examples :
Input : n = 47 Output: 1 // binary of n = 47 is 101111 Input : n = 549 Output: 3 // binary of n = 549 is 1000100101 Input : n = 1030 Output: 7 // binary of n = 1030 is 10000000110 Input : n = 8 Output: -1 // There is only one 1 in binary representation // of 8.
The idea to solve this problem is to use shift operator. We just need to find the position of two immediate 1’s in binary representation of n and maximize the difference of these position.
- Return -1 if number is 0 or is a power of 2. In these cases there are less than two 1’s in binary representation.
- Initialize variable prev with position of first right most 1, it basically stores the position of previously seen 1.
- Now take another variable cur which stores the position of immediate 1 just after prev.
- Now take difference of cur – prev – 1, it will be the number of 0’s between to immediate 1’s and compare it with previous max value of 0’s and update prev i.e; prev=cur for next iteration.
- Use auxiliary variable setBit, which scans all bits of n and helps to detect if current bits is 0 or 1.
- Initially check if N is 0 or power of 2.
Below is the implementation of the above idea :
C++
// C++ program to find maximum number of 0's // in binary representation of a number #include <bits/stdc++.h> using namespace std; // Returns maximum 0's between two immediate // 1's in binary representation of number int maxZeros( int n) { // If there are no 1's or there is only // 1, then return -1 if (n == 0 || (n & (n - 1)) == 0) return -1; // loop to find position of right most 1 // here sizeof int is 4 that means total 32 bits int setBit = 1, prev = 0, i; for (i = 1; i <= sizeof ( int ) * 8; i++) { prev++; // we have found right most 1 if ((n & setBit) == setBit) { setBit = setBit << 1; break ; } // left shift setBit by 1 to check next bit setBit = setBit << 1; } // now loop through for remaining bits and find // position of immediate 1 after prev int max0 = INT_MIN, cur = prev; for ( int j = i + 1; j <= sizeof ( int ) * 8; j++) { cur++; // if current bit is set, then compare // difference of cur - prev -1 with // previous maximum number of zeros if ((n & setBit) == setBit) { if (max0 < (cur - prev - 1)) max0 = cur - prev - 1; // update prev prev = cur; } setBit = setBit << 1; } return max0; } // Driver program to run the case int main() { int n = 549; // Initially check that number must not // be 0 and power of 2 cout << maxZeros(n); return 0; } |
Java
// Java program to find maximum number of 0's // in binary representation of a number class GFG { // Returns maximum 0's between two immediate // 1's in binary representation of number static int maxZeros( int n) { // If there are no 1's or there is only // 1, then return -1 if (n == 0 || (n & (n - 1 )) == 0 ) { return - 1 ; } //int size in java is 4 byte byte b = 4 ; // loop to find position of right most 1 // here sizeof int is 4 that means total 32 bits int setBit = 1 , prev = 0 , i; for (i = 1 ; i <= b* 8 ; i++) { prev++; // we have found right most 1 if ((n & setBit) == setBit) { setBit = setBit << 1 ; break ; } // left shift setBit by 1 to check next bit setBit = setBit << 1 ; } // now loop through for remaining bits and find // position of immediate 1 after prev int max0 = Integer.MIN_VALUE, cur = prev; for ( int j = i + 1 ; j <= b * 8 ; j++) { cur++; // if current bit is set, then compare // difference of cur - prev -1 with // previous maximum number of zeros if ((n & setBit) == setBit) { if (max0 < (cur - prev - 1 )) { max0 = cur - prev - 1 ; } // update prev prev = cur; } setBit = setBit << 1 ; } return max0; } // Driver program to run the case static public void main(String[] args) { int n = 549 ; // Initially check that number must not // be 0 and power of 2 System.out.println(maxZeros(n)); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program to find maximum number of # 0's in binary representation of a number # Returns maximum 0's between two immediate # 1's in binary representation of number def maxZeros(n): # If there are no 1's or there is # only 1, then return -1 if (n = = 0 or (n & (n - 1 )) = = 0 ): return - 1 # loop to find position of right most 1 # here sizeof is 4 that means total 32 bits setBit = 1 prev = 0 i = 1 while (i < 33 ): prev + = 1 # we have found right most 1 if ((n & setBit) = = setBit): setBit = setBit << 1 break # left shift setBit by 1 to check next bit setBit = setBit << 1 # now loop through for remaining bits and find # position of immediate 1 after prev max0 = - 10 * * 9 cur = prev for j in range (i + 1 , 33 ): cur + = 1 # if current bit is set, then compare # difference of cur - prev -1 with # previous maximum number of zeros if ((n & setBit) = = setBit): if (max0 < (cur - prev - 1 )): max0 = cur - prev - 1 # update prev prev = cur setBit = setBit << 1 return max0 # Driver Code n = 549 # Initially check that number must not # be 0 and power of 2 print (maxZeros(n)) # This code is contributed by Mohit Kumar |
C#
// C# program to find maximum number of 0's // in binary representation of a number using System; class GFG { // Returns maximum 0's between two immediate // 1's in binary representation of number static int maxZeros( int n) { // If there are no 1's or there is only // 1, then return -1 if (n == 0 || (n & (n - 1)) == 0) return -1; // loop to find position of right most 1 // here sizeof int is 4 that means total 32 bits int setBit = 1, prev = 0, i; for (i = 1; i <= sizeof ( int ) * 8; i++) { prev++; // we have found right most 1 if ((n & setBit) == setBit) { setBit = setBit << 1; break ; } // left shift setBit by 1 to check next bit setBit = setBit << 1; } // now loop through for remaining bits and find // position of immediate 1 after prev int max0 = int .MinValue, cur = prev; for ( int j = i + 1; j <= sizeof ( int ) * 8; j++) { cur++; // if current bit is set, then compare // difference of cur - prev -1 with // previous maximum number of zeros if ((n & setBit) == setBit) { if (max0 < (cur - prev - 1)) max0 = cur - prev - 1; // update prev prev = cur; } setBit = setBit << 1; } return max0; } // Driver program to run the case static public void Main() { int n = 549; // Initially check that number must not // be 0 and power of 2 Console.WriteLine(maxZeros(n)); } } // This code is contributed by vt_m. |
Javascript
<script> // JavaScript program to find maximum number of 0's // in binary representation of a number // Returns maximum 0's between two immediate // 1's in binary representation of number function maxZeros(n) { // If there are no 1's or there is only // 1, then return -1 if (n == 0 || (n & (n - 1)) == 0) { return -1; } // int size in java is 4 byte let b = 4; // Loop to find position of right most 1 // here sizeof int is 4 that means total 32 bits let setBit = 1, prev = 0, i; for (i = 1; i <= b* 8; i++) { prev++; // We have found right most 1 if ((n & setBit) == setBit) { setBit = setBit << 1; break ; } // Left shift setBit by 1 // to check next bit setBit = setBit << 1; } // Now loop through for remaining bits // and find position of immediate 1 after prev let max0 = Number.MIN_VALUE, cur = prev; for (let j = i + 1; j <= b * 8; j++) { cur++; // If current bit is set, then compare // difference of cur - prev -1 with // previous maximum number of zeros if ((n & setBit) == setBit) { if (max0 < (cur - prev - 1)) { max0 = cur - prev - 1; } // Update prev prev = cur; } setBit = setBit << 1; } return max0; } // Driver Code let n = 549; // Initially check that number must not // be 0 and power of 2 document.write(maxZeros(n)); // This code is contributed by code_hunt </script> |
Output:
3
Time Complexity: O(1), because it is taking constant time irrespective of the input n.
Auxiliary Space: O(1)
Contact Us