REV4 - Editorial

PROBLEM LINK:

Practice

Contest

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.

//