Working at a bit-wise level for this problem is a superior option than converting it to a string like the linked question (your inspiration) did.
There may be some really tricky magic that can be done with complicated AND/OR/XOR/NOT operations to identify the gaps in a more efficient way, but your solution of "walking" the bits is adequate from an algorithmic perspective.
Note, in your code you have special handling for negative values, but that's not needed if you use the >>>
operator for right shifting. Read up on the difference between signed and unsigned right shifts: http://docs.oracle.com/javase/specs/jls/se8/html/jls-15.html#jls-15.19
The recursion bothers me, though. The overhead for creating a stack frame for each level of recursion, calling the function, etc. seems overkill for something that would be "trivial" with a while-loop.
public static int maxGap(int n) {
// get rid of right-hand zeros
while (n != 0 && (n & 1) == 0) {
n >>>= 1;
}
int max = 0;
int gap = 0;
while (n != 0) {
if ((n & 1) == 0) {
gap++;
max = Math.max(gap, max);
} else {
gap = 0;
}
n >>>= 1;
}
return max;
}
Now, that runs in \$O(log(n))\$ time where n
is the integer being tested.... but, can it be a bit quicker?
I don't think the time complexity can be significantly improved (i.e. I can't see an \$O(1)\$ solution, but I can see some grunt performance improvements out there... assuming that Integer.numberOfTrailingZeros()
function is better than O(N) performance:
public static int maxGapX(int n) {
if (n == 0) {
return 0;
}
int rbits = Integer.numberOfTrailingZeros(n);
int max = 0;
// shift off any initial right-most zeros in the init step.
// then treat any subsequent 1's as the end of a span of zeros.
for (n >>>= (rbits + 1); n != 0; n >>>= (rbits + 1)) {
rbits = Integer.numberOfTrailingZeros(n);
max = Math.max(max, rbits);
}
return max;
}
I put this up in an ideone here: https://ideone.com/hllRUa
n
in terms of the bitcount and still look at an averageO(logn)
by searching for 0-intervals using devide and conquer (assuming a fulln
-bit integer zero-test isO(1)
) - you'd need to check all intervals.. so worst case stillO(n)
(101010..
->n/2
intervals)? \$\endgroup\$