Python Forum
Codility Binary Gap Exercise
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Codility Binary Gap Exercise
#1
Heya, rookie coder here trying to build up my know-how.
I've been working on this problem for far too long and was hoping I could get some insight here.
The current problem I'm facing is getting the program to invalidate series of zeros that don't end in a one, everything else seems to work as intended, albeit with delightfully sloppy novice code.
num = int(input('enter a number:'))
binlst = list()
streak = 0
while int(num) > 0 :
    if num > 2147483647 :
        print('integer too big')
        break
    bin = num % 2
    binlst.insert(0,bin)
    num = int(num / 2)
while len(binlst) < 8 :
    binlst.insert(0,0)
startone = None
dic = dict()
zeros = 0
for digit in binlst :
    if digit == 1 :
        dic = dict()
        startone = 0
    if digit == 0 and dic.get(zeros,0) == 0 :
        dic[zeros] = 1
    elif digit in dic :
        dic[zeros] = dic[zeros] + 1
    if dic.get(zeros,0) > 0 and dic.get(zeros,0) > streak and startone is not None :
        streak = dic.get(zeros,0)
print(binlst)
print('Longest streak of zeros:',streak)
Sample inputs and outputs:
In: 15, Out: 00001111 with streak 0 Cool
In: 42, Out: 00101010 with streak 1 Cool
In: 25, Out: 00011001 with streak 2 Cool
In: 32, Out: 00100000 with streak 5 Wall

Would love to hear some guidance on this,
Thanks!
Reply
#2
The solution for trailing zeros is actually contained in the description of binary gap; contiguous zeros surrounded by ones. So a gap will be preceded and followed by a 1.
set gap count and max gap to zero
set saw_one to False.
while number is greater than zero
    if number is odd this is the end of a gap.
        if saw_one
            Check if this was largest gap
        set gap count to zero
        set saw_one to True
    else 
        increment gap count
    shift number right
You have all the parts, but your logic on what to do when you see a 1 is a bit off. I see no reason to build a list of zeros and ones and then count using the list. Get rid of the list and count the zeros in the code that is getting the bits.
Reply
#3
I had the binary compiled into a list so it would be ordered properly.
e.g. integer 32 is 0100000 in the list whereas it's 0000001 otherwise
The output, however, was correct even if it wasn't ordered.
Here's the final, working code:
def solution(N):
    num = N
    streakstart = False
    streak = 0
    longstreak = 0
    while int(num) > 0 :
        bin = num % 2
        num = int(num / 2)
        if bin == 1 :
            streakstart = True
            streak = 0
        elif bin == 0 and streakstart is True :
            streak = streak + 1
        else :
            streak = 0
            continue
        if streak > longstreak :
            longstreak = streak
    return longstreak
    pass
Turns out I was just thinking too hard about it, thinking it needed proper binary order! Doh

Appreciate your help! <:
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  Codility Frog River One Westerner 2 2,342 Jan-09-2021, 06:35 PM
Last Post: deanhystad
  hex file to binary or pcap to binary baran01 1 5,630 Dec-11-2019, 10:19 PM
Last Post: Larz60+

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020