13

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.

1
  • The codility BinaryGap test allows for solutions written in 18 different languages: C, C++, C#, Go, Java 8, Java 11, JavaScript, Kotlin, Lua, Objective-C, Pascal, PHP, Perl, Python, Ruby, Scala, Swift 4, Visual Basic. So I don't see any reason to restrict this question to Python only.
    – Henke
    Jan 29, 2022 at 13:41

27 Answers 27

63

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')))  
7
  • 2
    Super nice :thumbsup: Jan 12, 2019 at 21:04
  • This one liner really very efficient. But I got stuck in one point, what is the functionality of strip? I ran that code without using strip and it had same output. Thank you in advance.
    – Encipher
    Mar 22, 2019 at 23:25
  • 5
    By definition binary gap is 'zeros between ones', therefore one should not consider trailing zeros as binary gap. Try to run both versions with int 32 (100000 in binary). With strip you get 0 (there is no binary gap) without strip you get 5 (which is incorrect as there is no 5 zeros between ones). Mar 25, 2019 at 7:23
  • If you are looking for performance: bin(), which @Orenico uses in his answers, is quite a bit faster than format(N, 'b').
    – quassy
    Jul 31, 2020 at 15:43
  • @quassy - please define 'quite a bit faster'. Casual check with timeit & Python 3.8 shows that format() is little bit faster than bin()[2:]. Same casual check also indicates that one can claim f"{N:b}" to be "quite a bit faster". Aug 1, 2020 at 13:57
14

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
9
  • 1
    I'd suggest using the int.bit_length method instead of the ceil(log2(...)) computation, to avoid corner-case errors due to rounding. Feb 23, 2018 at 16:00
  • You have said Your implementation converts the integer to a base two string then visits each character in the string but that is not completely correct as I break after detecting one then I split. Could you plz highlight why your implementation should be better in terms of time and memory complexity, please.
    – user8358337
    Feb 23, 2018 at 16:16
  • You still have to visit each character. How else can split find the right place to split? It visits each character until it finds the value you supplied. Feb 23, 2018 at 17:42
  • 1
    Hi Jean, Your code is much slower than the one I provided. I will add the time complexity in the answer (as running time test code).
    – user8358337
    Feb 26, 2018 at 8:45
  • 1
    Thanks, Jean. In the beginning, i was afraid to publish my codes in StackOverflow (negative comments), but you really encouraged me to keep on going (publish and optimize). Good luck
    – user8358337
    Feb 27, 2018 at 10:11
7
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
1
  • Welcome to Stack Overflow! Thank you for the code snippet, which might provide some limited, immediate help. A proper explanation would greatly improve its long-term value by describing why this is a good solution to the problem, and would make it more useful to future readers with other similar questions. Please edit your answer to add some explanation, including the assumptions you've made.
    – sepehr
    Oct 24, 2018 at 15:08
2

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.

2

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
2
  • This is the part of review answer in stackoverflow. Add some explanation though code is explanatory. Nov 16, 2018 at 13:20
  • Add explanation. Jan 17, 2019 at 9:52
2
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)
0
2

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
1

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
1

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
1

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')))

1

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)
1
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
0

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
0
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)
0

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
0
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
1
0
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
1
  • 1
    Can you explain your code? Dropping code without doing so might not be that helpful.
    – pzaenger
    Jan 19, 2020 at 12:17
0
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
1
  • 1
    Please explain why your answer is better than the others. This will help people learn from your answer. Feb 2, 2020 at 14:06
0

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)))
0

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
0

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
0

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.
0

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])
1
  • Please provide additional details in your answer. As it's currently written, it's hard to understand your solution.
    – Community Bot
    Sep 5, 2021 at 17:13
0
def solution(N):
    return len(max(bin(N).strip('0').split('1')[1:]))
1
  • Does this offer any benefit over other solutions offered here? Please edit to explain. Dec 17, 2021 at 0:46
0
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)
-1
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)
-1
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)
6
  • 1
    This works fine with any "Binary Gap " Lesson 1 codility Oct 9, 2018 at 3:48
  • 2
    While this code may answer the question, providing additional context regarding how and/or why it solves the problem would improve the answer's long-term value.
    – Nic3500
    Oct 9, 2018 at 4:32
  • Your code does not even run, because of the missing indention. Please fix that!
    – hellow
    Oct 9, 2018 at 6:22
  • @hellow, I had problems while posting . The code works absolutely fine . Oct 10, 2018 at 1:14
  • 2
    Then please read stackoverflow.com/editing-help and stackoverflow.com/help/how-to-answer . There is a ton of help available how to format your answer properly, so please don't use that as an excuse ;) (I don't drive a car, before I took some driving lessons. That's (nearly) the same. Read the instructions first and post afterwards)
    – hellow
    Oct 10, 2018 at 6:00