3

I read a little bit and found python-longest-binary-gap SO question

def solution(N):
    max_gap = 0
    new_gap = 0
    for i in range(N.bit_length()):
        if N & (1 << i):
            if new_gap > max_gap:
                max_gap = new_gap
            new_gap =0
        else:
            new_gap += 1
    if new_gap > max_gap:
        max_gap = new_gap
    return max_gap

The problem is that it gives the wrong solution for 32 (5 instead of 0) or 64. How to fix this?

Richard Rublev
  • 7,718
  • 16
  • 77
  • 121
  • 2
    Use PyCharm as your IDE and learn to use the debugger. Step through your code, line by line, examining the value of variables, and the answer will be obvious. You don't need us for questions like this - just your debugger :-) – Mawg says reinstate Monica Dec 21 '19 at 08:53
  • 1
    Some of the answers in the question you link to address this problem – Thierry Lathuille Dec 21 '19 at 08:59
  • 1
    It is because you start counting from the first bit even if it's zero. You need to start counting only when encountering a 1. I am really amazed this gets so upvoted, just a piece of code with "why this not working" AND with a link to the answer... – Tomerikoo Dec 21 '19 at 09:31
  • @RichardRublev yes, the community version is excellent, ***and*** it is free even for commercial use. I have used that paid/pro version, but even most companies I work for only use the community edition, and it is more than good enough – Mawg says reinstate Monica Dec 21 '19 at 11:23

2 Answers2

1

I marked new_gap=-1 until we encounter an actual bit-1.

def solution(N):
    max_gap = 0
    new_gap = -1
    for i in range(N.bit_length()):
        if N & (1 << i):
            if new_gap > max_gap:
                max_gap = new_gap
            new_gap = 0
        elif new_gap >= 0:
            new_gap += 1
    if new_gap > max_gap:
        max_gap = new_gap
    return max_gap 

# test
for i in range(1,33):
    print(i, solution2(i))

Output:

1 0
2 1
3 0
4 2
5 1
6 1
7 0
8 3
9 2
10 1
11 1
12 2
13 1
14 1
15 0
16 4
17 3
18 2
19 2
20 2
21 1
22 1
23 1
24 3
25 2
26 1
27 1
28 2
29 1
30 1
31 0
32 5
9mat
  • 1,194
  • 9
  • 13
1

Here's a pandas solution to this problem:

import pandas as pd

def getlargestgap(x):
  df = pd.DataFrame(list(map(list, bin(x)[2:])), columns=['A'])
  df['B'] = df.groupby(df.A.ne(df.A.shift()).cumsum()).cumcount()+1 
  df['Truth'] = df['A'] == '0'
  return df.loc[df['Truth'] == True]['B'].max() 

getlargestgap(23432124)

# 4
oppressionslayer
  • 6,942
  • 2
  • 7
  • 24