Skip to main content
5 of 8
added 70 characters in body
Roland Illig
  • 21.4k
  • 2
  • 34
  • 83

Your current code allocates several objects on the heap even though it doesn't need to. A string, a character array and several character objects.

Puzzles like this can often be solved not by inspecting the individual bits but by processing them in parallel. An alternative approach is:

To find the binary gap of n:

  • Discard all trailing zeros.
  • As long as n does not consist of 1s only:
    • Combine n with n shifted to the right by one place.
  • The number of repetitions is the length of the largest gap.

Taking 1000010001000 as an example:

1000010001   after 0 steps
1100011001   after 1 step
1110011101   after 2 steps
1111011111   after 3 steps
1111111111   after 4 steps

It took 4 steps, therefore the binary gap is 4.

In Java, this code becomes:

public static binaryGap(int n) {
    n >>>= Integer.numberOfTrailingZeros(n);
    int steps = 0;
    while ((n & (n + 1)) != 0) {
        n |= n >>> 1;
        steps++;
    }
    return steps;
}

As said in the above description, this code runs in \$\mathcal O(\text{gap})\$. It can be made to run in \$\mathcal O(\log_2 \text{gap})\$ by first taking 16 steps at once, then 8, then 4, then 2, then 1. This would make the code a little longer though. For understanding the underlying concept, the above code is better than the optimized version.

Roland Illig
  • 21.4k
  • 2
  • 34
  • 83