*We are given an integer value and we are expected to provide the information about the length of the longest sequence of 0s in its bits representation, but the solution should be not worst than O(log N). In example 167 = 10100111, the answer is 2.*

O(log N) for this problem? It’s gonna be freaking tricky outstanding solutions that moves the limits of algorithms up to the boundaries and even a step behind! Let’s take a look at the code firstly and then we will explain what are we doing.

int maxZeroLen(int N)
{
int maxLen = 0;
int curLen = 0;
while(N)
{
int remainder = N % 2;
N = N >> 1;
if(!remainder)
curLen++;
else curLen = 0;
maxLen = max(maxLen, curLen);
}
return maxLen;
}

Yes it is that simple. Sorry if you expected some magic here. When we divide by 2, we actually decrease the size of the problem in the logarithmic fashion 1/2, 1/4, 1/8… etc. So the solution is O(log N). I really like this problem as it makes you think and explains what logarithmic complexity really is.

Best Regards

Joe Kidd

### Like this:

Like Loading...

*Related*

Whoops, looks like a typo on line 8, it should say, “N = N >> 1”.

Thanks!