Find longest sequence of zeros in binary of an integer

One of my student asked me, following question about longest sequence of zeros in binary representation of an integer. You all knows the binary representation of any integer is in the form of 0’s and 1’s. So for example, we have an Integer 8, how we can calculate its binary. Following are steps to calculate binary of an integer.

  1. Divide 8 by 2, remainder is 0 and Quotient is 4
  2. Now Divide 4 by 2, remainder is 0 and Quotient is 2
  3. Divide 2 by 2, remainder is 0 and Quotient is 1
  4. We cannot divide further and stopped here, the Binary will be

Last Quotient, All remainders in reverse order

8 = 1000

Similarly for 9, binary representation will be 1001. Now let’s understand what binary gap is? Longest sequence of zeros are the number of zeros between two 1’s. In 9, we have two zeros between 1’s.

For Integer 529, the binary representation is 1000010001, now there are two substrings of ZERO’s. The numbers of zeros between first and second 1 are 4 and the number of zeros between second and last 1 are 3, so the longest sequence of zeros will be 4.  

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.

Write a program that find the longest sequence of zeros in binary representation of an integer. Follow these rules

  • Numbers having only one 1 in binary, the longest sequence will be 0 (No binary gap)
  • N is an integer within the range [1..2,147,483,647] i-e Number must be greater than 0.

Let’s solve this problem step by;

For positive number, we can simply write

def solution(N):
    if int(N) <= 0:
        return "Number should be greater than 0"

How to calculate the binary of an Integer in Python?

We can use the default function ‘bin()’ to calculate binary of an integer.

bin(32)
'0b100000'

Now the binary number will be in the form of string like object, we need to remove first two character from this.

N = 32
N = str(bin(N))[2:]
print(N)
'100000'

Find all positions where the character is 1 in binary number. We can use simple logic to do that. Loop through all indices, if character is 1, store that index in array. For Integer 529, the binary is 1000010001, and the bins will be:-

bins = [0, 5, 9]

Next step is to find length of all substrings between above indices, like

0(+1) to 5 = substring (0000) length is 4

5(+1) to 9 = substring (000) length is 3

Note: (+1), because on this index the value will be 1, but we need only ZERO’s we add 1 to skip binary number “1”.

Now we have any array of binary gaps, simply find the max number and return that number. In this example the longest binary gap will be 4.

Write all above code snippets in one function “solution”, following is the complete code to calculate longest binary gap of zeros in an Integer.

Try Code here:

def solution(N):
    if N <= 0:
        return "Number should be greater than 0"
    
    N = str(bin(N))[2:]
    
    bins = []
    for i in range(0, len(N)):
        if str(N)[i] == "1":
            bins.append(i)
    
    binary_gaps = []
    for i in range(len(bins)-1):
        print(N[bins[i]+1:bins[i+1]])
        binary_gaps.append(len(N[bins[i]+1:bins[i+1]]))
    if binary_gaps == []:
        return 0
    
    return max(binary_gaps)
solution(32)
0
solution(529)
4
solution(-10)
"Number should be greater than 0"

Try other challenge: Function that returns Maximum Possible Value, Given an Integer

Reference: https://app.codility.com/programmers/lessons/1-iterations/binary_gap/

44990cookie-checkFind longest sequence of zeros in binary of an integer

Leave a Reply