Length of the Longest Consecutive 1s in Binary Representation
Given a number N, The task is to find the length of the longest consecutive 1s series in its binary representation.
Examples :
Input: N = 14
Output: 3
Explanation: The binary representation of 14 is 1110.Input: N = 222
Output: 4
Explanation: The binary representation of 222 is 11011110.
Naive Approach: Below is the idea to solve the problem
Traverse the bits of binary representation of N and keep a track of the number of consecutive set bits, and the maximum length of consecutive 1s found so far.
Time Complexity: O(X), Here X is the length of binary representation of N.
Auxiliary Space: O(1)
Find the length of the longest consecutive 1s series using Bit Magic:
Below is the idea to solve the problem:
The idea is based on the concept that the AND of bit sequence with a left shifted by 1 version of itself effectively removes the trailing 1 from every sequence of consecutive 1s.
So the operation N = (N & (N << 1)) reduces length of every sequence of 1s by one in binary representation of N. If we keep doing this operation in a loop, we end up with N = 0. The number of iterations required to reach 0 is actually length of the longest consecutive sequence of 1s.
Illustration:
11101111 (x)
& 11011110 (x << 1)
—————————
11001110 (x & (x << 1))
^ ^
| |Trailing 1 removed
Follow the below steps to implement the above approach:
- Create a variable count initialized with value 0.
- Run a while loop till N is not 0.
- In each iteration perform the operation N = (N & (N << 1))
- Increment count by one.
- Return count
Below is the Implementation of above approach:
C++
// C++ program to find length of the longest // consecutive 1s in binary representation of // a number. #include<bits/stdc++.h> using namespace std; int maxConsecutiveOnes( int x) { // Initialize result int count = 0; // Count the number of iterations to // reach x = 0. while (x!=0) { // This operation reduces length // of every sequence of 1s by one. x = (x & (x << 1)); count++; } return count; } // Driver code int main() { // Function Call cout << maxConsecutiveOnes(14) << endl; cout << maxConsecutiveOnes(222) << endl; return 0; } |
Java
// Java program to find length of the longest // consecutive 1s in binary representation of // a number. class MaxConsecutiveOnes { private static int maxConsecutiveOnes( int x) { // Initialize result int count = 0 ; // Count the number of iterations to // reach x = 0. while (x!= 0 ) { // This operation reduces length // of every sequence of 1s by one. x = (x & (x << 1 )); count++; } return count; } // Driver code public static void main(String strings[]) { System.out.println(maxConsecutiveOnes( 14 )); System.out.println(maxConsecutiveOnes( 222 )); } } |
Python3
# Python program to find # length of the longest # consecutive 1s in # binary representation of # a number. def maxConsecutiveOnes(x): # Initialize result count = 0 # Count the number of iterations to # reach x = 0. while (x! = 0 ): # This operation reduces length # of every sequence of 1s by one. x = (x & (x << 1 )) count = count + 1 return count # Driver code print (maxConsecutiveOnes( 14 )) print (maxConsecutiveOnes( 222 )) # This code is contributed # by Anant Agarwal. |
C#
// C# program to find length of the // longest consecutive 1s in binary // representation of a number. using System; class GFG { // Function to find length of the // longest consecutive 1s in binary // representation of a number private static int maxConsecutiveOnes( int x) { // Initialize result int count = 0; // Count the number of iterations // to reach x = 0. while (x != 0) { // This operation reduces length // of every sequence of 1s by one. x = (x & (x << 1)); count++; } return count; } // Driver code public static void Main() { Console.WriteLine(maxConsecutiveOnes(14)); Console.Write(maxConsecutiveOnes(222)); } } // This code is contributed by Nitin Mittal. |
Javascript
<script> // Javascript program to find length // of the longest consecutive 1s in // binary representation of a number. function maxConsecutiveOnes(x) { // Initialize result let count = 0; // Count the number of iterations to // reach x = 0. while (x != 0) { // This operation reduces length // of every sequence of 1s by one. x = (x & (x << 1)); count++; } return count; } // Driver code document.write(maxConsecutiveOnes(14) + "<br/>" ); document.write(maxConsecutiveOnes(222)); // This code is contributed by code_hunt </script> |
PHP
<?php // PHP program to find length // of the longest consecutive // 1s in binary representation of // a number. function maxConsecutiveOnes( $x ) { // Initialize result $count = 0; // Count the number of // iterations to reach x = 0. while ( $x != 0) { // This operation reduces // length of every sequence // of 1s by one. $x = ( $x & ( $x << 1)); $count ++; } return $count ; } // Driver code echo maxConsecutiveOnes(14), "\n" ; echo maxConsecutiveOnes(222), "\n" ; // This code is contributed by Ajit ?> |
3 4
Time Complexity: O(log X), Here X is the length of binary representation of N
Auxiliary Space: O(1)
Approach 2: Using String Conversion
Here’s a brief explanation of the algorithm:
We start by initializing max_len and cur_len to 0. Then, we iterate through the bits of the given integer n. If we encounter a 1 bit, we increment cur_len. If we encounter a 0 bit, we update max_len if cur_len is greater than max_len, and reset cur_len to 0. This is because a 0 bit breaks the current run of consecutive 1s. Finally, we return max_len.
- Initialize a variable max_len to 0 to store the length of the longest consecutive 1s found so far.
- Initialize a variable cur_len to 0 to store the length of the current consecutive 1s.
- While the integer n is not equal to 0, perform the following steps:
- If the least significant bit (LSB) of n is 1, increment cur_len.
- If the LSB of n is 0, update max_len if cur_len is greater than max_len, and reset cur_len to.
- Right shift n by 1 bit.
- If cur_len is greater than max_len, update max_len.
- Return max_len.
C++
// C++ program to find the length of the longest // consecutive 1s in binary representation of // a number. #include <iostream> #include <bitset> #include <string> using namespace std; int main() { int num = 222; // Convert the integer to its binary representation as a string string binary = bitset<32>(num).to_string(); int count = 0; int maxCount = 0; // Loop through the binary string to find the longest consecutive 1s for ( int i = 0; i < binary.size(); i++) { if (binary[i] == '1' ) { count++; if (count > maxCount) { maxCount = count; } } else { count = 0; } } // Print the result cout << "The length of the longest consecutive 1s in the binary representation is: " << maxCount << endl; return 0; } |
Java
// Java program to find the length of the longest // consecutive 1s in binary representation of // a number. import java.util.Arrays; public class LongestConsecutiveOnes { public static void main(String[] args) { int num = 222 ; // Convert the integer to its binary representation as a string String binary = String.format( "%32s" , Integer.toBinaryString(num)).replace( ' ' , '0' ); int count = 0 ; int maxCount = 0 ; // Loop through the binary string to find the longest consecutive 1s for ( int i = 0 ; i < binary.length(); i++) { if (binary.charAt(i) == '1' ) { count++; if (count > maxCount) { maxCount = count; } } else { count = 0 ; } } // Print the result System.out.println( "The length of the longest consecutive 1s in the binary representation is: " + maxCount); } } |
Python3
# Python program to find the length of the longest # consecutive 1s in binary representation of # a number. def main(): num = 222 # Convert the integer to its binary representation as a string binary = format (num, '032b' ) count = 0 max_count = 0 # Loop through the binary string to find the longest consecutive 1s for i in range ( len (binary)): if binary[i] = = '1' : count + = 1 if count > max_count: max_count = count else : count = 0 # Print the result print ( "The length of the longest consecutive 1s in the binary representation is:" , max_count) if __name__ = = "__main__" : main() |
C#
// C# program to find the length of the longest // consecutive 1s in binary representation of // a number. using System; public class LongestConsecutiveOnes { public static void Main( string [] args) { int num = 222; // Convert the integer to its binary representation as a string string binary = Convert.ToString(num, 2).PadLeft(32, '0' ); int count = 0; int maxCount = 0; // Loop through the binary string to find the longest consecutive 1s for ( int i = 0; i < binary.Length; i++) { if (binary[i] == '1' ) { count++; if (count > maxCount) { maxCount = count; } } else { count = 0; } } // Print the result Console.WriteLine( "The length of the longest consecutive 1s in the binary representation is: " + maxCount); } } |
Javascript
// JavaScript program to find the length of the longest // consecutive 1s in binary representation of // a number. function main() { const num = 222; // Convert the integer to its binary representation as a string let binary = num.toString(2).padStart(32, '0' ); let count = 0; let maxCount = 0; // Loop through the binary string to find the longest consecutive 1s for (let i = 0; i < binary.length; i++) { if (binary[i] === '1' ) { count++; if (count > maxCount) { maxCount = count; } } else { count = 0; } } // Print the result console.log( "The length of the longest consecutive 1s in the binary representation is:" , maxCount); } main(); |
The length of the longest consecutive 1s in the binary representation is: 4
The time complexity of this algorithm is O(log n), where n is the given integer, since we iterate through the bits of the integer. The space complexity is O(1), since we only use constant extra space to store the variables max_len and cur_len.
Contact Us