Kirk
BAN USERI know. That's why I said terminate adding zeroes after odd number is encountered and then calculate in the same way for i/2 if for i/2 it is greater than what was for i then the max cont number of zeroes is the one for i. Sorry if it wasn't clear
e.g
suppose 38
38 is even so max=1;
19 odd so max[2]=0;
9 odd so max[3]=0;
4 even so max[4]=1;
2 even so max[4]=2;
1 odd so max[5]=0;
max=2
now check if it's correct
38 0
19 1
9 1
4 0
2 0
1 1
100110
0+2+4+32=38
max cont = 2;
The logic would be to recursively do this->
if i is divisible by 2 then add 1 to max number of zeroes of max number of zeroes of i/2;
if i is odd then terminate adding and calculate max number of zeroes for i/2 and compare the max zeroes before i to the max zeroes by i/2
max for 1 is 0
I think this should work fine with log n complexity since we are going on dividing it by 2.
Okay so we have to take N= number of bits. Got it.
- Kirk October 27, 2013