Python: Find longest binary gap in binary representation of an integer number

Question

I would like to know if my implementation is efficient. I have tried to find the simplest and low complex solution to that problem using python.

def count_gap(x):
    """
        Perform Find the longest sequence of zeros between ones "gap" in binary representation of an integer

        Parameters
        ----------
        x : int
            input integer value

        Returns
        ----------
        max_gap : int
            the maximum gap length

    """
    try:
        # Convert int to binary
        b = "{0:b}".format(x)
        # Iterate from right to lift 
        # Start detecting gaps after fist "one"
        for i,j in enumerate(b[::-1]):
            if int(j) == 1:
                max_gap = max([len(i) for i in b[::-1][i:].split('1') if i])
                break
    except ValueError:
        print("Oops! no gap found")
        max_gap = 0
    return max_gap

let me know your opinion.

Answer 1

I do realize that brevity does not mean readability nor efficiency.

However, ability to spell out solution in spoken language and implement it in Python in no time constitutes efficient use of my time.

For binary gap: hey, lets convert int into binary, strip trailing zeros, split at '1' to list, then find longest element in list and get this element lenght.

def binary_gap(N):
    return len(max(format(N, 'b').strip('0').split('1')))  

Answer 2

Your implementation converts the integer to a base two string then visits each character in the string. Instead, you could just visit each bit in the integer using << and &. Doing so will avoid visiting each bit twice (first to convert it to a string, then to check if if it's a "1" or not in the resulting string). It will also avoid allocating memory for the string and then for each substring you inspect.

You can inspect each bit of the integer by visiting 1 << 0, 1 << 1, ..., 1 << (x.bit_length).

For example:

def max_gap(x):
    max_gap_length = 0
    current_gap_length = 0
    for i in range(x.bit_length()):
        if x & (1 << i):
            # Set, any gap is over.
            if current_gap_length > max_gap_length:
                max_gap_length = current_gap_length
            current_gap_length = 0
         else:
            # Not set, the gap widens.
            current_gap_length += 1
    # Gap might end at the end.
    if current_gap_length > max_gap_length:
        max_gap_length = current_gap_length
    return max_gap_length

Answer 3

def max_gap(N):
    xs = bin(N)[2:].strip('0').split('1')
    return max([len(x) for x in xs])

Explanation:

1. Both leading and trailing zeros are redundant with binary gap finding as they are not bounded by two 1's (left and right respectively)
2. So step 1 striping zeros left and right
3. Then splitting by 1's yields all sequences of 0'z
4. Solution: The maximum length of 0's sub-strings

Answer 4

As suggested in the comments, itertools.groupby is efficient in grouping elements of an iterable like a string. You could approach it like this:

from itertools import groupby

def count_gap(x):
    b = "{0:b}".format(x)
    return max(len(list(v)) for k, v in groupby(b.strip("0")) if k == "0")

number = 123456
print(count_gap(number))

First we strip all zeroes from the ends, because a gap has to have on both ends a one. Then itertools.groupby groups ones and zeros and we extract the key (i.e. "0" or "1") together with a group (i.e. if we convert it into a list, it looks like "0000" or "11"). Next we collect the length for every group v, if k is zero. And from this we determine the largest number, i.e. the longest gap of zeroes amidst the ones.

Answer 5

I think the accepted answer dose not work when the input number is 32 (100000). Here is my solution:

def solution(N):
    res = 0
    st = -1
    for i in range(N.bit_length()):
        if N & (1 << i):
            if st != -1:
                res = max(res, i - st - 1)
            st = i

    return res

Answer 6

def solution(N):
    # write your code in Python 3.6
    count = 0
    gap_list=[]
    bin_var = format(N,"b")
    for bit in bin_var:
        if (bit =="1"):
            gap_list.append(count)
            count =0
        else:
            count +=1
    return max(gap_list)

Answer 7

Here is my solution:

def solution(N):
    num = binary = format(N, "06b")
    char = str(num)
    find=False
    result, conteur=0, 0

    for c in char:
        if c=='1' and not find:
            find = True
            
        if find and c=='0':
            conteur+=1

        if c=='1':
            if result<conteur:
                result=conteur
            conteur=0

    return result

Answer 8

this also works:

def binary_gap(n):
    max_gap = 0
    current_gap = 0

    # Skip the tailing zero(s)
    while n > 0 and n % 2 == 0:
        n //= 2

    while n > 0:
        remainder = n % 2
        if remainder == 0:
            # Inside a gap
            current_gap += 1
        else:
            # Gap ends
            if current_gap != 0:
                max_gap = max(current_gap, max_gap)
                current_gap = 0
        n //= 2

    return max_gap

Answer 9

Old question, but I would solve it using generators.

from itertools import dropwhile

# a generator that returns binary 
# representation of the input
def getBinary(N):
    while N:
        yield N%2
        N //= 2

def longestGap(N):
    longestGap = 0
    currentGap = 0

    # we want to discard the initial 0's in the binary
    # representation of the input
    for i in dropwhile(lambda x: not x, getBinary(N)):
        if i:
            # a new gap is found. Compare to the maximum
            longestGap = max(currentGap, longestGap)
            currentGap = 0
        else:
            # extend the previous gap or start a new one
            currentGap+=1

    return longestGap

Answer 10

Can be done using strip() and split() function : Steps:

1. Convert to binary (Remove first two characters )
2. Convert int to string
3. Remove the trailing and starting 0 and 1 respectively
4. Split with 1 from the string to find the subsequences of strings
5. Find the length of the longest substring

Second strip('1') is not mandatory but it will decrease the cases to be checked and will improve the time complexity Worst case T

def solution(N):
    return len(max(bin(N)[2:].strip('0').strip('1').split('1')))

Answer 11

def solution(N: int) -> int:
    binary = bin(N)[2:]
    longest_gap = 0
    gap = 0
    for char in binary:
        if char == '0':
            gap += 1
        else:
            if gap > longest_gap:
                longest_gap = gap
            gap = 0
    return longest_gap

Answer 12

def solution(N):
# write your code in Python 3.6

    iterable_N = "{0:b}".format(N)
    max_gap = 0
    gap_positions = []
    for index, item in enumerate(iterable_N):
        if item == "1":
            if len(gap_positions) > 0:
               if (index - gap_positions[-1]) > max_gap:
                    max_gap = index - gap_positions[-1]
            gap_positions.append(index)
    max_gap -= 1 
    return max_gap if max_gap >= 0 else 0

Answer 13

Solution using bit shift operator (100%). Basically the complexity is O(N).

def solution(N):
    # write your code in Python 3.6
    meet_one = False
    count = 0
    keep = []
    while N:
        if meet_one and N & 1 == 0:
            count+=1
        
        if  N & 1:
            meet_one = True
            keep.append(count)
            count = 0
        N >>=1

    return max(keep)

Answer 14

this also works:

def solution(N):
    bin_num = str(bin(N)[2:])
    list1 = bin_num.split('1')
    max_gap =0
    if bin_num.endswith('0'):
        len1 = len(list1) - 1
    else:
        len1 = len(list1)
    if len1 != 0:
        for i in range(len1):
            if max_gap < len(list1[i]):
                max_gap = len(list1[i])
    return max_gap

Answer 15

def solution(number):

    bits = [int(digit) for digit in bin(number)[2:]]
    occurences = [i for i, bit in enumerate(bits) if(bit==1)]
    res = [occurences[counter+1]-a-1 for counter, a in enumerate(occurences) if(counter+1 < len(occurences))]

    if(not res):
        print("Gap: 0")
    else:
        print("Gap: ", max(res))

number = 1042
solution(number)

Answer 16

This works

def solution(number):
    # convert number to binary then strip trailing zeroes
    binary = ("{0:b}".format(number)).strip("0")
    longest_gap = 0
    current_gap = 0
    for c in binary:
        if c is "0":
           current_gap = current_gap + 1
        else:
           current_gap = 0

        if current_gap > longest_gap:
           longest_gap = current_gap 


    return longest_gap

Answer 17

def max_gap(N):
    bin = '{0:b}'.format(N)
    binary_gap = []
    bin_list = [bin[i:i+1] for i in range(0, len(bin), 1)] 

    for i in range(len(bin_list)):
        if (bin_list[i] == '1'):
            # print(i)
            # print(bin_list[i])
            # print(binary_gap)
            gap = []
            for j in range(len(bin_list[i+1:])):
                # print(j)
                # print(bin_list[j])
                if(bin_list[i+j+1]=='1'):
                    binary_gap.append(j)
                    # print(j)
                    # print(bin_list[j])
                    # print(binary_gap)
                    break
                elif(bin_list[i+j+1]=='0'):
                    # print(i+j+1)
                    # print(bin_list[j])
                    # print(binary_gap)
                    continue
                else:
                    # print(i+j+1)
                    # print(bin_list[i+j])
                    # print(binary_gap)
                    break
        else:
            # print(i)
            # print(bin_list[i])
            # print(binary_gap)
            binary_gap.append(0)


    return max(binary_gap)
    pass

Answer 18

def find(s, ch):
    return [i for i, ltr in enumerate(s) if ltr == ch]

def solution(N):
    get_bin = lambda x: format(x, 'b')
    binary_num = get_bin(N)
    print(binary_num)
    binary_str = str(binary_num)
    list_1s = find(binary_str,'1')
    diffmax = 0
    for i in range(len(list_1s)-1):
        if len(list_1s)<1:
            diffmax = 0
            break
        else:
            diff = list_1s[i+1] - list_1s[i] - 1
            if diff > diffmax:
                diffmax = diff
    return diffmax
    pass

Answer 19

Here's a solution using iterators and generators that will handle edge cases such as the binary gap for the number 32 (100000) being 0 and the binary gap for 0 being 0. It doesn't create a list, instead relying on iterating and processing elements of the bit string one step at a time for a memory efficient solution.

def solution(N):
    def counter(n):
        count = 0
        preceeding_one = False
        for x in reversed(bin(n).lstrip('0b')):
            x = int(x)
            if x == 1:
                count = 0
                preceeding_one = True
                yield count
            if preceeding_one and x == 0:
                count += 1
                yield count
        yield count
    return(max(counter(N)))

Answer 20

Here is one more that seems to be easy to understand.

def count_gap(x):
     binary_str = list(bin(x)[2:].strip('0'))
     max_gap = 0 
     n = len(binary_str)
     pivot_point = 0

     for i in range(pivot_point, n):
         zeros = 0
         for j in range(i + 1, n):
              if binary_str[j] == '0':
                   zeros += 1 
              else:
                   pivot_point = j
                   break

         max_gap = max(max_gap, zeros)

     return max_gap

Answer 21

This is really old, I know. But here's mine:

def solution(N):
    gap_list = [len(gap) for gap in bin(N)[2:].strip("0").split("1") if gap != ""]
    
    return max(gap_list) if gap_list else 0

Answer 22

Here is another efficient solution. Hope it may helps you. You just need to pass any number in function and it will return longest Binary gap.

def LongestBinaryGap(num):

n = int(num/2)
bin_arr = []

for i in range(0,n):
    if i == 0:
        n1 = int(num/2)
        bin_arr.append(num%2)
    else:
        bin_arr.append(n1%2)
        n1 = int(n1/2)

        if n1 == 0:
            break

print(bin_arr)
result = ""
count = 0
count_arr = []

for i in bin_arr:
    if result == "found":
        if i == 0:
            count += 1
        else:
            if count > 0:
                count_arr.append(count)
                count = 0
    if i == 1:
        result = 'found'
    else:
        pass

if len(count_arr) == 0:
    return 0
else:
    return max(count_arr)

print(LongestBinaryGap(1130))  # Here you can pass any number.

Answer 23

My code in python 3.6 scores 100 Get the binary Number .. Get the positions of 1 get the abs differennce between 1.. sort it

 S = bin(num).replace("0b", "")
          res = [int(x) for x in str(S)]
          print(res)
          if res.count(1) < 2 or res.count(0) < 1:
              print("its has no binary gap")
          else: 
            positionof1 = [i for i,x in enumerate(res) if x==1]
            print(positionof1)
            differnce = [abs(j-i) for i,j in zip(positionof1, positionof1[1:])]
            differnce[:] = [differnce - 1 for differnce in differnce]
            differnce.sort()
            print(differnce[-1])

Answer 24

def solution(N):
    return len(max(bin(N).strip('0').split('1')[1:]))

Answer 25

def solution(N):
    maksimum = 0 
    zeros_list = str(N).split('1')
    if zeros_list[-1] != "" :
        zeros_list.pop()
        
    for item in zeros_list :
        if  len(item) > maksimum :
            maksimum = len(item)
    return(maksimum)

Answer 26

def solution(N):
    bin_num = str(bin(N)[2:])
    bin_num = bin_num.rstrip('0')
    bin_num = bin_num.lstrip('0')
    list1 = bin_num.split('1')
    max_gap = 0

    for i in range(len(list1)):
        if len(list1[i]) > max_gap:
            max_gap = len(list1[i])

    return (max_gap)

Answer 27

def solution(N):
    # Convert the number to bin 
    br = bin(N).split('b')[1]
    sunya=[]
    groupvalues=[]
    for i in br:
        count = i
        if int(count) == 1:
            groupvalues.append(len(sunya))
            sunya=[]
        if int(count) == 0:
            sunya.append('count') 

    return max(groupvalues)