Efficient way of BinaryGap

Question

A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N.

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. The number 32 has binary representation 100000 and has no binary gaps.

Write a function:

class Solution { public int solution(int N); }

that, given a positive integer N, returns the length of its longest binary gap. The function should return 0 if N doesn't contain a binary gap.

For example, given N = 1041 the function should return 5, because N has binary representation 10000010001 and so its longest binary gap is of length 5. Given N = 32 the function should return 0, because N has binary representation '100000' and thus no binary gaps.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..2,147,483,647].

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import javax.swing.plaf.basic.BasicInternalFrameTitlePane.MaximizeAction;

public class Main {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Solution s = new Solution();
        int x = s.solution(1041);

        System.out.println(x);
    }


}

class Solution { 

    public int solution(int N) 
    {
        int countZero = 0;
        Integer maxCountZeroList = 0;

        List<Integer> countZeroList = new ArrayList<Integer>();

        String nBin = Integer.toBinaryString(N);
        for (int i=1;i<nBin.length();i++) {

            if(nBin.charAt(i) == '1')
            {
                countZeroList.add(countZero);
                countZero = 0;
            }
            else
            {
                countZero++;
            }

        }

        if(countZeroList.size() > 0) 
        {
            maxCountZeroList = Collections.max(countZeroList);
        }
        return maxCountZeroList;
    } 
}

I am looking for more efficient way of solution of this problem

Answer 1

Unused Imports

import javax.swing.plaf.basic.BasicInternalFrameTitlePane.MaximizeAction;

This is never used, so why have it?

Useless Comments

// TODO Auto-generated method stub

Clearly, you've implemented the method. Remove the TODO comment.

Singletons

Solution s = new Solution();
int x = s.solution(1041);

Solution is a class with no data members, just one function. There is no reason to make an instance of this class, just make the method static. Actually, there is no obvious reason to have the Solution class; you can make solution() a static member function in Main.

Pointless Box

Integer maxCountZeroList = 0;

There is no reason to have maxCountZeroList an object. An int would be sufficient. Since solutions() returns an int, and ends with return maxCountZeroList;, you are unboxing this integer anyway.

One Pass

You are doing two passes over your data. The first pass you are counting non-'1' characters, and storing the counts in a List. The second pass, this time over the list, you are looking for the max() value.

This can be done in one pass.

int countZero = 0;
int maxCountZero = 0;

String nBin = Integer.toBinaryString(N);
for (int i=1;i<nBin.length();i++) {

    if(nBin.charAt(i) == '1')
    {
        if (countZero > maxCountZero)
            maxCountZero = countZero;

        countZero = 0;
    }
    else
    {
        countZero++;
    }

}
return maxCountZero;

Enhanced For Loop

Instead of looping over the indices of nBin, and then calling .charAt() at each index (the only place the index is used), you could instead loop over the characters of the string, eliminating the need for the .charAt() call.

for (char ch : nBin.toCharArray()) {

    if(ch == '1')
    {
        if (countZero > maxCountZero)
            maxCountZero = countZero;

        countZero = 0;
    }
    else
    {
        countZero++;
    }

}

Looking for the wrong thing

This code is not counting "zeros". It is counting "not ones". It would be clearer written as:

for (char ch : nBin.toCharArray()) {

    if(ch == '0')
    {
        countZero++;
    }
    else
    {
        if (countZero > maxCountZero)
            maxCountZero = countZero;

        countZero = 0;
    }
}

---

Efficiency Improvement

@Harshal's improved solution is a bit obfuscated, but it does run in \$O(gap)\$ time. Here is a less obfuscated implementation which runs in \$O({numGaps})\$ time.

int max_gap = 0;

n >>>= Integer.numberOfTrailingZeros(n);   // Get rid of ending 0's.
n >>>= Integer.numberOfTrailingZeros(~n);  // Get rid of ending 1's.

while (n > 0) {
    int gap = Integer.numberOfTrailingZeros(n);
    if (gap > max_gap)
        max_gap = gap;

    n >>>= gap;
    n >>>= Integer.numberOfTrailingZeros(~n);
} 

return max_gap;

Assuming Integer.numberOfTrailingZeros(x) executes in constant time, the above while loop will execute once for each "gap", computing exactly how long each gap is. With 0x40000001, Harshal's method must loop 31 times, where as this algorithm loops only once. In contrast, with 0x55555555, this algorithm loops 15 times, finding each gap of one '0', where as Harshal's algorithm loops once; the maximum gap size.

Profiling, and knowledge of the distribution of values, will be important in choosing between the two optimizations.

Answer 2

Your code works. But can be improved.

Your current code allocates several objects on the heap even though it doesn't need to. Also, the Collections.max takes a lot of time.

I have a completely different approach here. So I will just post the code I wrote some time ago (maybe a couple of years ago). It looks something like this:

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

Try to understand the code by adding some print statements. Post a comment if you have any questions.

Some tests:

Method "solution" Answer: 5
Time Taken: 393061 nanoseconds
Method "binaryGap" Answer: 5
Time Taken: 26053 nanoseconds

As you can see here, "solution" method is about 15 times slower than the "binaryGap" method because this code runs in O(gap), which is a bit better than O(bits).

Hope this helps. Good luck.