PROBLEM LINK:
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Bit Manipulation
PROBLEM:
Find the largest number of consecutive set bits in a given number.
EXPLANATION:
The problem becomes easy once you find the logic.
You can find the maximum number of consecutive bits by incrementing the count whenever the bit is 1 and if the bits is 0, by updating current maximum and resetting the count.
count=max=0
while n is not 0
if LSB is 1 //LSB- Least Significant Bit
count=count+1
else
if count > max
max=count
count=0;
n=n/2
if count > max
max=count
The complexity of this solution is O(log n).
ALTERNATIVE SOLUTIONS:
You can first convert the number into its binary form and store it as a string. Then, using a for loop, do the same thing given above but instead of checking the LSB you can check each character in the binary string.
The binary representation can be found in O(log n) and finding the maximum number of consecutive set bits is also O(log n). So this approach also takes O(log n).
But we can do better than O(log n) using the approach discussed here. If the maximum number of consecutive set bits is k, then this approach has a complexity O(k).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
First Tester’s solution can be found here.
Both of the solutions above use O(log n) approach.
Second Tester’s solution can be found here.
This Solution uses the O(k) approach.