5
\$\begingroup\$

For example, number 9 has binary representation 1001 and contains a binary gap of length 2. The number 529 has binary representation 1000010001 and contains two binary gaps: one of length 4 and one of length 3. The number 20 has binary representation 10100 and contains one binary gap of length 1. The number 15 has binary representation 1111 and has no binary gaps.

I'd like to know how this would be performance wise, and if there is a better way to do it.

public int solution(int N) {
    int binaryGap = 0;
    String binaryString = Integer.toBinaryString(N);
    char[] characters = binaryString.toCharArray();
    int j = 0;
    Character c;
    for (int i = 0; i < characters.length; i++) {
         c = characters[i];
        if (c.equals('0')) {
            j += 1;
        }

        if (c.equals('1')) {
            if (j > binaryGap ){
                binaryGap = j;
            }
            j = 0;
        }

    }
    System.out.println(binaryGap);
    return binaryGap;

}
\$\endgroup\$
5
\$\begingroup\$

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})\$, which is a bit better than \$\mathcal O(\text{bits})\$.

It might be worth making it run in \$\mathcal O(\log_2 \text{gap})\$ by first taking 16 steps at once, then 8, then 4, then 2, then 1. If that's possible at all. For 32 bits it's entirely possible to compare all results of the optimized version against the simple code shown above. But then I guess the code will become much more complicated.

\$\endgroup\$
3
\$\begingroup\$

Tweaks

    Character c;
    for (int i = 0; i < characters.length; i++) {
         c = characters[i];

You can write this more simply as

    for (Character c : characters) {

Then i is Java's problem.

Plus, this is clearer. It says directly what is being done. For each character in the string, do these things.

            j += 1;

You could write this as

            j++;

which is more idiomatic.

        }

        if (c.equals('1')) {

You could replace this with either

        } else if (c == '1') {

or

        } else {

After all, what else would it be? It's a binary string. And obviously you don't have to check that it's not '0'. You just did that.

You don't need to use equals with a character, as it reduces to a primitive type (char). You can do so here, but you don't have to do so.

I'd move the println outside the method. Then you can choose to output or not.

Performance

Very little of that will make any performance difference. What could though would be to stop mucking with strings. It's possible to work directly with the integer.

public static int solution(int N) {
    int binaryGap = 0;

    if (N == 0) {
        return 0;
    }

    // remove trailing zeroes if not counted; credit to Peter Taylor
    while (N % 2 == 0) {
        N /= 2;
    }

    for (int j = 0; N > 0; N /= 2) {
        if (N % 2 == 0) {
            j++;
        } else {
            if (j > binaryGap) {
                binaryGap = j;
            }

            j = 0;
        }
    }

    return binaryGap;
}

This is essentially what the Integer.toBinaryString does to build the string. Doing it like this means that we don't have to do it twice.

You could also use bit operations instead of division and modulus. Ideally the compiler should do that for you if it would be faster. But you could benchmark instead.

There's an argument that you should leave the declaration of j outside the for loop. Since you don't iterate over j. But you also don't use j outside the loop, so the scope is right this way.

\$\endgroup\$
  • \$\begingroup\$ There is one subtle difference between the OP's code and your inline base conversion approach (which I'm aware of because it came up in a code review I did of a question with a slightly different spec). OP's code ignores trailing zeroes. The fix is either while (N % 2 != 0) { N /= 2; } or N /= N & (1 + ~N);. \$\endgroup\$ – Peter Taylor Apr 3 '17 at 8:07
  • \$\begingroup\$ Thanks! Having never really looked at binary before I didn't think of doing it with integers, but that makes a lot of sense \$\endgroup\$ – Cormack Apr 3 '17 at 8:23
  • \$\begingroup\$ @PeterTaylor Why so complicated? ;) Instead of N /= N & (1 + ~N) you can also write N /= N & -N, which is equivalent. \$\endgroup\$ – Roland Illig May 3 at 16:29
2
\$\begingroup\$

There's a small issue with your algorithm, and is that it will calculate the binary gap even if doesn't exist, like with a 6 (110) it will return one instead of zero, my suggestion will be just add a flag like:

public static int solution(int N) {
    int binaryGap = 0;
    boolean found_one = false;

    for (int j = 0; N > 0; N /= 2) {
        if (N % 2 == 0) {
            j++;
        } else {
            if (j > binaryGap && found_one == true){
                binaryGap = j;
            }
            found_one = true;
            j = 0;
        }
    }

    return binaryGap;
}
\$\endgroup\$
  • \$\begingroup\$ The uppercase N looks like a constant but isn't. It should be named lowercase n. The found_one flag should be named foundOne instead, to follow the Java naming conventions. The == true is redundant. \$\endgroup\$ – Roland Illig Apr 15 at 21:40
  • \$\begingroup\$ the upper case N is an annoyance that Codility seems to do with all it's variable names. messes me up when I'm trying to type code fast in it's exams. \$\endgroup\$ – flyingdrifter Jul 31 at 4:10
2
\$\begingroup\$

Firstly, you should make N constant by putting final modifier in front of it in the prototype.

Secondly, Java implements strings using a character array, there is no performance gain in converting the string to an array (binaryString.charAt(i) takes the same amount of time as characters[i]). Also, using the class Character with .equals is actually hurting performance, as creating a class and using .equals takes longer than using the char type and == operator. So, you can slightly increase the space and time complexity of your program. But since it is so basic, you wouldn't notice it with an integer, you'd probably not notice the difference with a BigInteger.

Lastly, one small improvement you can make in the logic of your method is checking how many digits are left in your string. For example, if you have the string 100001001, by the time you get to the second 1, there is no possible way the binary gap could be larger than what you have already found, since there are only 3 digits left, but you found a gap of size 4, in best case the next one could only be 2, no need to continue checking, so just return.

\$\endgroup\$

protected by Community Jan 7 '18 at 22:53

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.