### 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.