I was recently doing Codility tests for practice. I, for once decided that it would be good to practice these things instead of just read them and absorb nothing. The one documented below is the BinaryGap. Essentially the task is find longest sequence of zeros in binary representation of an integer, ignoring those that are not bound on either side with a one.

To explain the code, and why I did what I did.
First thing I did was to convert the integer to a binary string, this was then trimmer as the requirement says you must ignore all trailing spaces “The number 32 has binary representation 100000 and has no binary gaps.” My test case here failed the first time because I didn’t read correctly.

string bits = Convert.ToString(N, 2).TrimEnd('0');

Next thing to do is to decide what we are looking at, and count the occurrence or ignore the occurrence. I initially tried to do this with a switch case, but the interesting thing that I found about the Codility compiler is that it wouldn’t accept

case "0" when count > 0

. So writing this in a switch statement was out of the question. It was that or perhaps just me.

Next part actually in nor really complicated, it just the clock is ticking and it makes you make errors. First thing we need to do is check if we have already started counting, if we haven’t in this iteration, then we fall through to the next if statement, reason for this is that we need to assume performance wse that every iteration here after is a zero.
Second time round, we increment the counter with one, if it’s a one then we ignore it.

if (t == '0' && count > 0)
	count++;
else if (t == '0')
	count = 1;
else
	count = 0;

or I guess it could be represented as such just not as readable, but interestingly if you go count++ then it fails a test case, I suspect that’s because its trying to increment and assign at the same time.

count = (t == '0' && count > 0) ? count + 1: (t == '0') ? 1 : 0;

Lastly, we need to compare if this is the largest BinaryGap.

“given a positive integer N, returns the length of its longest binary gap.”

This is simply done by checking to see if the count is larger then the longest number counted thus far and then recording that as the new longest count.

if (count > longest) longest = count;

So with this all said and done the complete solution would look something like this.

        public static int solution(int N)
        {
            string bits = Convert.ToString(N, 2).TrimEnd('0');
            //Console.Write(bits);
            // Variable for holding longest binary gap
            int longest = 0, count = 0;
 
            foreach (var t in bits)
            {
                if (t == '0' && count > 0)
                    count++;
                else if (t == '0')
                    count = 1;
                else
                    count = 0;
 
                if (count > longest) longest = count;
            }
            //Console.Write(longest);
            return longest;
        }

Leave a Reply

You must be logged in to post a comment.