Codility ‘BinaryGap’ Solution

Short Problem Definition:

Find longest sequence of zeros in binary representation of an integer.

Link

BinaryGap

Complexity:

expected worst-case time complexity isΒ O(log(N));

expected worst-case space complexity is O(1)

Execution:

The solution is straight-forward! Use of binary shift.

Solution:
def solution(N):
    cnt = 0
    result = 0
    found_one = False

    i = N    
        
    while i:
        if i & 1 == 1:
            if (found_one == False):
                found_one = True
            else:
                result = max(result,cnt)
            cnt = 0
        else:
            cnt += 1
        i >>= 1
   
    return result

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
  • Nico
  • satish jonnala

    def solution(N):
    binstr = bin(N)[2:].strip(“0”)
    binlst = str(binstr).split(“1”)
    return len(max(binlst))

    Please grade my solution. It shows 100% correctness. But want to know if its a cleaner solution.
    Thanks

    • It’s certainly a nice idea. It took me something like 10 minutes to verify all details. (strip also strips from the beginning, max of [“00”, “000”] returns the longest string and not the lexicographically last, etc).

      Why do you cut off the first two characters of the array?

      • satish jonnala

        Hi Martin. Thanks for the reply. I’m cutting them because bin(decimal int) is giving me “0b” at the beginning of result – to indicate the binary representation.

    • Your solution actually seems to be faster https://ideone.com/rymo2p
      8.53875207901s
      vs
      2.49804401398s

    • Sarim Bob


      def solution(n)
      binstr = n.to_s(2).gsub(/(^[0]*)|([0]*$)/, '')
      binlst = binstr.split('1')
      binlst = binlst.sort!
      if binlst.size == 0 then return 0 else return binlst.last.length end
      end

      this is my solution in ruby that i got based on your solution

  • Stan

    Please could you help me comment the codes for easy understanding. I am still learning, and I get lost in all the codes. Pleaseee I beg of you!

    • what would you need?

      • Stan

        Please some explanations, as comments to the codes, to enable me understand the codes step by step. As much as you can do. I really appreciate. Thank you

        • I can help out with concrete questions. If there is something that you do not understand, ask away. Keep in mind that I can not know what you understand and what not.

  • Adi

    Correct me if I am wrong, but after line 11 “found_one = True” don’t you need a “cnt = 0”, otherwise for 10100 you would get 3 instead of 1?

    • The specification says: “A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N.” 10100 should result in 1. Not in 2 (because 100 is not surrounded). You need to discard everything before you find the first 1.

      • Adi

        That is correct, and is what I am saying. I was giving 10100 as an example in which the above code will give an incorrect answer (3) instead of the correct one (1) because it is missing the statement cnt = 0 after line 11.

        • It does not.

          >>> solution(20)
          1

          Are you sure that when you copy-pasted the code, you got the indentation right?

          • Adi

            Sorry you are right, I read it as only part of the else statement. I have to get use to python, I wrote the code in C# πŸ˜€

          • Haha πŸ™‚ cool! Wanna share your C# version?

          • Adi

            public int solution(int N)
            {

            var maxBinaryGap = 0;
            var zeroCount = 0;
            var foundFirst = false;

            while (N != 0)
            {
            if ((N & 1) == 1)
            {
            if (foundFirst == false)
            {
            foundFirst = true;
            }
            else
            {
            maxBinaryGap = Math.Max(maxBinaryGap, zeroCount);
            }
            zeroCount = 0;
            }
            else
            {
            zeroCount++
            }
            N >>= 1;
            }
            return maxBinaryGap;
            }

  • Shru

    Hello,
    why are we doing this part?

    if (found_one == False):
    found_one = True
    else:
    result = max(result,cnt)

  • Chinedu Olebu

    def solution(N):
    A = (bin(N))[2:]
    l = len(A)
    i = 0
    List = []
    count = 0
    temp = 0
    while(i < l):
    if(A[i] == '1' and temp == 0):
    temp = 1
    if(temp == 1):
    if(A[i] == '0'):
    count += 1
    else:
    List.append(count)
    count = 0
    i += 1
    return max(List)

  • Chinedu Olebu