# Codility ‘BinaryGap’ Solution

##### Short Problem Definition:

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

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.

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

• oh! π

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

• Stan

LIke in the code, I do not understand the following statements in the while Loop:

while i:
if i & 1 == 1:
if (found_one == False):
found_one = True

Why do we need to assign i & 1==1. Why not just i?
And why should found_one=True?

• if i & 1 == 1 is a binary operation, not an assignment. You do a binary AND on i and 1 and check, whether the result is equal to 1. It is the binary trick that answers the question “is the last bit set (is a 1)”. Look into https://wiki.python.org/moin/BitwiseOperators, https://www.codecademy.com/courses/python-intermediate-en-KE1UJ/0/1

• Stan

Thank you so much

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.

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?

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?

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

• to remove leading 0 blocks.

• Isaac

why do we need to do the test :
if (found_one == False):
found_one = True

can we not skip this one ?

Thanks very much!

• 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
• Pppa Kn

This is C# solution. I got 100%.

class Solution {
public int solution(int N) {
int zeroCount = 0;
int maxCount = 0;
string str = Convert.ToString(N, 2).ToString();
for (int i = 0; i maxCount)
{
maxCount = zeroCount;
}
zeroCount = 0;
}
}
}
return maxCount;
}
}

• Kartika Mulia

Java Version:

class Solution {
public int solution(int N) {
int zeroCount = 0;
int maxCount = 0;
String[] str = Integer.toString(N,2).split(“”);
for (int i = 0; i maxCount) {
maxCount = zeroCount;
}
zeroCount = 0;
}
}
}

return maxCount;
}
}

• satish

private static long maxConsecutiveZeroes(int x) {

boolean flagOne = false;

long count = 0, max = 0;

//Loop until x becomes 0.

while (x != 0) {

if ((x & 1) == 1) {

flagOne = true;

if (count > max) {

max = count;

}

count = 0;

} else if (flagOne) {

count += 1;

} else {

count += 1;

}

x = x >> 1;//Move ht binary digits to right side bit by bit.

}

return max;

}

http://techno-terminal.blogspot.in/2017/03/find-longest-sequence-of-zeros-in.html

• Salman Hanif

Hi i would like the code in javascript

• Rajesh Wellington
• Nicolas

I understand the solutions, yet they all seem to me like they take O(N) time as opposed to the O(logN) that is asked. What am i missing?

• the solution is O(N) as far as the number of digits is concerned. There is log(N) number of digits in any number. Does that help?

• Nicolas

Ah, i thought N represented an already binary number. Thank you!