Binary Gap Exercise in Codility

Suppose a positive integer N is given. Determine the binary representation of N, and find the longest subsequence of the form 10*1 in this representation, where 0* stands for any number of zeros in the sequence. Examples: 11, 101, 1001, 10001 etc. Return the number of zeros in the longest sequence you found. If you didn’t find such a sequence, return zero.

You can read the original task description on Codility.

Solution:

Whenever you deal with a riddle, bear in mind, it doesn’t matter what techniques you use as long as your solution is correct. Don’t try to impress your interviewers with fancy techniques, don’t even think about announcing that you are going to use “functional programming” or “recursion” or anything else. Just get the job done.

Do explain your thought process! If you are on the right track, your interviewers will appreciate relating to how you think. If you are on the wrong track, your interviewers will often help you out, because they relate to you, and they want you to succeed.

You can read more interviewing tips in The Developer’s Edge.

Before coding, always plan your solution, and explain how you want to solve your task. Your interviewers may correct you, and in the best case, say that you can start coding. In our case, the plan looks as follows:

1. Convert N into a binary string
2. Set a sequence counter to zero. Set a maximum sequence counter to zero.
3. Iterate over each digit of the binary representation
   • If you find a zero, increase the sequence counter by one.
   • If you find a one, compare the sequence counter to the maximum sequence counter, and save the higher value in the maximum sequence counter. Then set the sequence counter to zero to read the upcoming sequence lengths.
4. Once you finish, return the maximum sequence counter value.

Obtaining the binary representation:

You may or may not know that integers have a toString method, and the first argument of toString is the base in which the number should be interpreted. Base 2 is binary, so all you need to do to convert an integer into its binary representation is: