Codility Challenge: My Binary Gap Positive Integer Solution (Python)

For fun, education and self development I like to get involved with open source projects and coding challenges online. One of the most well known is online code test platforms is Codility.

Especially in Japan. Many of the top recruiters of developers, like Indeed, Google and Rakuten will use Codility and other testing platforms to test your ability to code efficient and scalable code.

The task

* The following blockquote is directly taken from the Codility website. Copyright remains exclusively to Codility. The use of the text here is for educational purposes only.

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.

Examples:

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

Write a function:

def solution(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].

Smaller pieces are easier to digest

Let's take the task and break it down into smaller pieces, I often find that by doing it this way helps me develop my applications as a well structured whole.

What is it we actually want to achieve

From the task, we are to return the maximal sequence of consecutive zeros from the result of an integer converted if there is at least a single 0 after an instance of 1 and before the next 1. Basically, we just need to count all the 0 that fall between a 1 and a 1. Each time this happens we say it is a new group, we then need to find the group with the highest amount of zeros in it.

For example, If we take the number 29210 do some simple and quick maths we get the binary representation of:

Next we need to create the groups of zeros that fall between a 1 and 1. Using the above binary we can ascertain that there are 3 groups.

Finally, we need to return the length of the largest group. In this example the largest group is GROUP 2 and the length to be returned is: 4

So how do we do that in Python?

1. Convert the Integer (N) into it's binary representation counterpart

Python comes with some built in functions and luckily one of these is bin(). This function takes an input of type Integer and returns a binary string prefixed with 0b

If we use an online Python compiler such as: repl.it we can check our code straight away.

Go to that website, and in the left panel where you type in your Python code, input:

This will give us the result: 0b1

We do not want the 0b at the beginning for our example so we can escape it using [2:], this is part of the built in regular expressions. By adding [2:] to the end we are saying do not get the first two characters of the string. Now, The code should look like:

This will give us the result: 1

Using the above example of converting text to binary, to achieve that here we would use something like:

This will give us the result: 111001000011010

2. Work out what the groups are and return the largest

Now we need to build the mechanism that will work out the groups of zeros as depicted above. Whenever you are faced with the task of defining a programs logic, it's best to use a flowchart. A flowchart is a representation of the workflow of an application, an algorithm or process.

A flowchart will allow you to check your programs logic with different scenarios (test cases). To start with our flowchart we must first work out what parts of the mechanism we need to have. For this specific task, I would suggest that our code will do the following things:

• Loop through the returned string of integers (br)
• Check if following character after a 1 is a 0
• Check if following character after a 0 is a 1
• Start counting for a group
• Stop counting for a group
• Get the total for the current group
• Check if current total is higher than any previous totals
• Store highest group total

3. Putting it all together

Start looping through the string, The Codility test gives us our inputs as N and suggests we pass them into our Solution() function. like so:

def solution(N)

which means, we need to change our binary replace string above to:

br = str(bin(N))[2:]

Let's also define some variables that we will use to; 1) Check if a new group count has started, 2) record the highest group so far and 3) Count the 0's in the group.

br_group = False
br_highest = 0
bin_zero_counter = 0

Next, we'll loop through (using the python ForLoop) the returned binary converted string of characters:

for char in br:

This will assign each iteration character to that loop instance of char. For example, using the returned string of 110011, each instant of the loop would change the value of char:

1. char = 1
2. char = 1
3. char = 0
4. char = 0
5. char = 1
6. char = 1

Each loop iteration allows us to run a block of code. Inside this we can use the python if statement to check the first part of our flowchart, if its true, run some code. However, we can also run code if it is not true:

# Check first condition:
if char == '1':
    # Run code needed if true
elif {condition} :
    # Run code needed if not true

What we need here is to add an incremented value to the group counter as if the returned string is not a 1 then it will be a 0. The above function then will change to:

# Check first condition:
if char == '1':
    # Run code needed if true
elif br_group:
    bin_zero_counter += 1

In our 'if true' block, we start the group tracker by setting br_group to true and we set the bin_zero_counter to 0

br_group = True
bin_zero_counter = 0

We do need to check however if the current counter is higher than the highest recorded

if br_highest < bin_zero_counter:
    br_highest = bin_zero_counter

And that sums up the breakdown of the code.

Completed code

When we put it all together we get:

And when we run it in the Codility validator, we get the result of:

View online result report