3

Trying a solution for the problem listed here in python, I thought I'd try a nice little regex to capture the maximum "binary gap" (chains of zeroes in the binary representation of a number).

The function I wrote for the problem is below:

def solution(N):
    max_gap = 0
    binary_N = format(N, 'b')
    list = re.findall(r'1(0+)1', binary_N)

    for element in list:
        if len(element) > max_gap:
            max_gap = len(element)

    return max_gap

And it works pretty well. However... for some reason, it does not match the second set of zeroes in 10000010000000001 (binary representation of 66561). The 9 zeroes don't appear in the list of matches so it must be a problem with the regex - but I can't see where it is as it matches every other example given!

3
  • I think you just need list = re.findall(r'1(0+)', binary_N). No need to consume the right-hand side 1. Jan 26, 2016 at 12:10
  • According to the instructions about complexity, would your algorithm meet the requirements (expected worst-case time complexity is O(log(N)))? I thought about using regex but then kept it simple not using any module. 1st question: Would using regex add or substract any points? Or does it depend on the examiner? 2nd question: I came up with this solution: pastebin.com/TNhx37JG How good or bad is it? If I had to guess, I would say the complexiy is O(N) (because I have to iterate through all bits), but I can't guess how would it be with O(log(N)). Any help would be amazing. Thanks!
    – vabada
    Mar 23, 2016 at 0:20
  • Well as tested, it does meet the requirements, although I'll admit it is bending the rules slightly by using regex... have you tried your solution on the codility website?
    – Barnabus
    Mar 29, 2016 at 15:05

1 Answer 1

7

The same bit can't be included in two matches. Your regex matches a 1 followed by one or more 0s and ends with another 1. Once the first match has been found you are left with 0000000001 which doesn't start with a 1 so isn't matched by your regex.

As mentioned by @JoachimIsaksson, if you want to match both sets of 0s, you can use a lookahead so that the final 1 is checked but isn't included in the match. r'1(0+)(?=1)'.

2
  • 4
    +1. As a bonus , you can use a lookahead in the regex to make it not match (and eliminate) the trailing one; r'1(0+)(?=1)' Jan 26, 2016 at 12:01
  • Thanks @JoachimIsaksson, I've added that in.
    – Holloway
    Jan 26, 2016 at 12:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.