Solution to Binary-Gap by codility

29 Jan

January 29, 2014 Sheng 85

Question: https://codility.com/demo/take-sample-test/binary_gap

Question Name: BinaryGap

def solution(N):

max_gap = 0

current_gap = 0

# Skip the tailing zero(s)

while N > 0 and N%2 == 0:

N //= 2

while N > 0:

remainder = N%2

if remainder == 0:

# Inside a gap

current_gap += 1

else:

# Gap ends

if current_gap != 0:

max_gap = max(current_gap, max_gap)

current_gap = 0

N //= 2

return max_gap

85 Replies to “Solution to Binary-Gap by codility”

K says:
August 11, 2014 at 2:01 pm
Do you think, mine is a good solution? I got a score of 100 but I’m new to python..
https://codility.com/demo/results/demoEPJM3K-G24/
Reply
- Sheng says:
  August 11, 2014 at 2:51 pm
  Yes, your solution is good. Actually my solution is kind of bad. I should use more bit operations rather than math operations.
  Reply
  - Dario Cangialosi says:
    October 4, 2018 at 2:34 am
    N>>=1 N&1
    as bit-wise equivalent operations
    Reply
- uri says:
  August 12, 2019 at 7:21 am
  I saw your code and is vary good, but I have an idea to improve
  1
  2
  if temp- bg> sl-i:
  return temp
  
  it will make your code a bit more efficient
  Reply
Pa says:
November 12, 2014 at 8:31 pm
Hi Sheng, I really appreciate if you can tell me why “K: solution (posted in his link in the comments) has the complexity of Logn. I think it should be O(n) since we see every bit once.
Please advise. Thank you!
Reply
- Sheng says:
  November 12, 2014 at 11:27 pm
  Hello!
  N is the original number. And the number of bits in it is log2(N).
  Reply
Mikhail says:
February 27, 2015 at 12:37 pm
Guys, please judge my solution https://codility.com/demo/results/demoZK5TWJ-945/. What do you think?
Reply
- Sheng says:
  March 5, 2015 at 1:26 am
  Be confident please! Your solution is pretty good! Only one small suggestion:
  Use “return max(b)” instead of “b.sort(); return b[-1]”
  The former is O(N), while the latter is O(NlogN).
  Reply

Here’s my C++ solution for which I get 100%

int solution(int N) {

int longestGap = 0;

int gap = 0;

int ones = 0; // number of 1's detected

// count longest gap by checking each bit of N

while( N != 0){

// check if LSB(N) = 0 or 1

if(N & 0x01) ones++;

else if(ones) gap++;

// Gap is found for every two 1's detected

if(ones == 2) {

ones = 1;

longestGap = max(longestGap, gap);

gap = 0; // reset gap

}

N >>= 1;

}

return longestGap;

}

Shaon says:
April 19, 2016 at 10:38 am
Hello,
how does it work with tailing zeros.
n=51712=110010100000000 and n=20=10100
codality shows it correct, but the program has no logic when first tailing LSB is zero.
I used this code in my IDE, and it doesn’t work with the two numbers I mentioned, however, codality analysis says your code works perfectly for these two numbers.
I am confused. Would you please tell me how your code works when for it finds zero at LSB in the first cycle of the while loop.
Reply
- Sheng says:
  April 19, 2016 at 8:18 pm
  It does consider the tailing zeros. Please refer to the line #12: “else if(ones) gap++;”, while initially “ones” is 0. In other words, for the tailing zeros, the conditions for lines #11 #12 and #15 are all false. Eventually, the program skips the tailing zeros.
  Reply

My php solution, 100%

function solution($N) {

$count = 0;

$tab = explode("1",decbin($N));

if ($tab[sizeof($tab)-1]!="") array_pop($tab);

for ($i=0;$i<sizeof($tab);$i++){

if ($tab[$i]!="") {

$gap[] = strlen($tab[$i]);

}

if (sizeof($gap) > 0) {

$count=max($gap);

return $count;

} else return 0;

}

Even more simpler with PHP:)

function solution($n)

{

$result = [];

$tab = explode("1", decbin($n));

foreach ($tab as $t) {

if ($t != "") {

$result[] = $t;

}

if (!empty($result)) {

return $maxlen = max(array_map('strlen', $result));

} else {

return 0;

}

My C solution, 100%: https://codility.com/demo/results/trainingBUPAMC-8KR/

int solution(int N) {

// write your code in C99

int max = 0;

int state = 3; // state 0: last encountered a '0'

// state 1: last encountered a '1'

// state 3: start

int bitmask = 0x00000001;

int loopmax = 0;

while (bitmask > 0){

//printf("Bitmask = 0x%08xn", bitmask);

//printf("loopmax = %dn", loopmax);

if((bitmask & N) != 0){

//printf("Encountered a 1n");

if(state != 1){

state = 1;

if(loopmax > max){

max = loopmax;

}

loopmax = 0;

}

else { // '0'

if(state == 3); // nothing

else {

state = 0;

loopmax++;

}

bitmask = bitmask << 1;

}

return max;

}

John Doe says:
January 21, 2016 at 8:12 am
Could you talk me through your soluton please, thanks!
Reply
Mayur says:
December 7, 2019 at 11:54 pm
how the code works if N is more than 8 bits in binary.
Reply
- Sheng says:
  December 8, 2019 at 12:07 am
  The question description says: N is an integer within the range [1..2,147,483,647].
  I think, Colby’s code is assuming the input is 32 bits, since the bitmask is 32bits.
  Reply

mark soliman says:
December 29, 2015 at 3:46 am
My solution using C#
https://codility.com/demo/results/trainingYTJ5PV-3N7/
Reply
- Ileana says:
  December 12, 2016 at 3:28 am
  where is the code?
  Reply
  - Sheng says:
    December 12, 2016 at 9:51 pm
    Click the link and you will see it.
    Reply

Here is my javascript solution
https://codility.com/demo/results/trainingYMPTHX-Z4S/

function solution(N) {

// write your code in JavaScript (Node.js 4.0.0)

var b = (N >>> 0).toString(2);

var g = b.split("1");

var m = g.length;

if(g[m-1] !== null) g.splice(m-1,m);

g = g.filter(Boolean)

var maxGap = 0;

var currentGap = 0;

for(var i=g.length-1;i>=0;i--){

currentGap = g[i].length;

if(currentGap > maxGap) maxGap = currentGap;

}

return maxGap;

}

w7gf83fgiwyfg says:
December 10, 2017 at 2:23 pm
Why do you need all this stuff? What are you trying to check?
1
2
3
4
    var b = (N >>> 0).toString(2);
    var g = b.split("1");
    var m = g.length;
    if(g[m-1] !== null) g.splice(m-1,m);

1
if(g[m-1] !== null)

is ALWAYS true. Why do you need it?
Reply
- Sheng says:
  December 14, 2017 at 6:14 am
  Try to remove that single line on Codility, and you’ll see the reason
  PS: I do not use Javascript. I do not know why.
  Reply

sashi says:
February 13, 2016 at 12:36 pm
In java . is it ok?
Edited by Admin: code was removed.
Reply
- Sheng says:
  February 14, 2016 at 10:10 pm
  hi Sashi, please read the guideline before posting code. Besides, for the correctness, why not to try codility’s OJ platform?
  Reply
ramusus says:
February 28, 2016 at 2:12 pm
What do you think about this solution
1
2
3
def solution(N):
gaps = "{0:b}".format(N).split('1')[1:-1]
return len(max(gaps)) if gaps else 0

Reply
- Sheng says:
  March 2, 2016 at 9:21 pm
  I think it’s very Pythonic and you are a master in Python
  Reply
- dev says:
  March 25, 2016 at 4:09 am
  Space complexity isn’t O(1) !
  Reply
  - Sheng says:
    April 4, 2016 at 7:43 pm
    You are right
    Reply
- mohamed_ayman says:
  May 11, 2019 at 11:38 pm
  But, the N could be < 647 in your code.
  Reply

Javascript Solution

function solution(N) {

// write your code in JavaScript (Node.js 4.0.0)

// https://codility.com/demo/results/trainingT4YUUR-XKN/

var tx = N.toString(2), l=tx.length, b = 0, t = 0, i=0;

while (i<l) {

if (tx[i]==="0") {

b++;

}

if (tx[i]=="1") {

if (t<b){

t=b;

}

b=0;

}

i++;

}

return t;

}

C# solution with Regex and Split

string binary = Convert.ToString(N, 2);

Regex regex = new Regex("1(.*)1");

Match chars = regex.Match(binary);

string binaryAfterRegex = chars.Value;

string[] gaps = binaryAfterRegex.Split('1');

int t = 0;

foreach (string txt in gaps)

{

if ((string.IsNullOrEmpty(txt)) == false)

{

while (txt.Length > t)

{

t = txt.Length;

}

return 0;

Sheng says:
April 4, 2016 at 7:35 pm
The while loop seems unnecessary.
Reply

Chaitanya says:
September 5, 2016 at 12:09 am
This works great and can you email me the explanation. Thanks for I appreciate your clean code.
Reply
- Sheng says:
  September 19, 2016 at 8:45 pm
  I believe these clean code is self-explanatory. Please try to read it.
  Reply

//java one

public int solution(int N) {

String str = Integer.toBinaryString(N);

str = str.replace("0", " ").trim();

String[] zeroGroups = str.split("1");

if (zeroGroups.length == 0) return 0;

int[] gaps = new int[zeroGroups.length];

for (int i = 0; i < zeroGroups.length; i++){

gaps[i] = zeroGroups[i].length();

}

Arrays.sort(gaps);

return gaps[gaps.length-1];

}

Here’s my way of doing it. Does it look unnecessarily long?

def BinGap(N):

maxNum = 0

myNum = int((bin(N)[2:]))

while myNum > 0:

while myNum % 10 == 1:

myNum //= 10

count = 0

while myNum > 0 and myNum % 10 ==0:

count += 1

myNum //= 10

maxNum = max(maxNum, count)

myNum //= 10

return maxNum

Sheng says:
April 16, 2016 at 7:53 pm
Not so long
Reply

why when n=51712 the answer should be 2 not 9?
>>> bin(51712)
‘0b1100101000000000’
medium1
n=51712=110010100000000_2 and n=20=10100_2 ✘WRONG ANSWER
got 9 expected 2
I see why 51712 is 2 not 9 – ending 1 is missing
this got 100

def solution(N):

# write your code in Python 2.7

x=bin(N)

max_0 = 0

counter = 0

arry = x[2:] if N > 0 else x[3:]

for i in arry:

if counter > max_0 and i == '1':

max_0 = counter

if i == '1':

counter = 0

else:

counter += 1

return max_0

Methor says:
April 23, 2016 at 3:26 am
My javaScript solution:
score: 100 of 100
Reply
- Sheng says:
  April 29, 2016 at 5:58 pm
  Sorry. Your submitted code is incomplete. Please read the “Guideline for Comments” firstly. Thanks!
  Reply

Hi Sheng,
The solutio below (Java) resulted in 100 score. I am not very satisfied with the use of the boolean flag and mathematical functions though.
Would you recommend some amendments?
Thanks!

class Solution {

int solution (int N){

String binaryString = Integer.toBinaryString(N);

int count = 0;

boolean flag = false;

char[] binaryChar = binaryString.toCharArray();

for (int i = 0, j = 0; i < binaryChar.length; i++)

{

if(flag || (binaryChar[i]) == '0' && i > 0 && binaryChar[i-1] == '1' && i < binaryChar.length-1){

flag = true;

if((binaryChar[i]) == '0')

j++;

}

if(binaryChar[i] == '1' && flag) {

flag = false;

if (j > count)

count = j;

j = 0;

}

return count;

}

Sheng says:
April 29, 2016 at 6:22 pm
First of all, please read the “Guideline for Comments” firstly, on the right column.
I briefly check your code. It should work. But there is some space to improve. My two cents are:
1. Rename the variable with more meaningful names, such as “flag” -> “in_gap”;
2. The logic inside for loop could be simplified. It is not so readable as these conditions.
Reply

Daniel says:
May 23, 2016 at 11:02 pm
C++ solution:
Reply
- Sheng says:
  May 24, 2016 at 9:10 pm
  Please refer to “Guideline for Comments” (in the right column) to post code. Thanks!
  Reply

Hi Sheng, here is my solution in Javascript.

function solution(N) {

// write your code in JavaScript (Node.js 4.0.0)

const binN = (N >>> 0).toString(2);

const untrailed = binN.slice(0, binN.lastIndexOf(1) +1);

return untrailed.split(1)

.filter(x => x.indexOf('0') > -1)

.reduce((val, acc) => val.length > acc.length ? val : acc, '')

.length;

}

Sheng says:
May 24, 2016 at 9:11 pm
Thanks for sharing!
Reply
Tonki Honks says:
September 13, 2017 at 10:33 am
Clever ES6 Lucas!
Reply

Here’s my 100% C# solution.

public int GetLargestBinaryGap(int N)

{

var matches = new Regex("(?<=1{1})([0]+)(?=1{1})").Matches(Convert.ToString(N, 2));

return (from object match in matches select match.ToString().Length).Concat(new[] {0}).Max();

}

Here’s a C# solution using bit shifting.

public static int GetLargestBinaryGap(int N) {

int count = 0;

int maxCount = 0;

bool isCounting = false;

while (N > 0) {

if ((N & 1) == 1) {

if (isCounting) {

if (count > maxCount) maxCount = count;

count = 0;

}

isCounting = true;

} else {

if (isCounting) count++;

}

N >>= 1;

}

return maxCount;

}

My 100% C# solution

public static int solution(int N)

{

string binaryNum = Convert.ToString(N, 2);

string match = Regex.Match(binaryNum, @"1[0].*1").Value;

return match.Split('1').Max(i => i.Length);

}

ss053 says:
July 4, 2016 at 2:25 am
My solution for Javascript
https://codility.com/demo/results/trainingFEWKVG-QEM/
Reply
Michiel van der Blonk says:
August 6, 2016 at 11:00 am
Here’s my JavaScript solution
Reply
- Sheng says:
  August 11, 2016 at 9:12 pm
  Please refer to the “Guideline for Comments” on the right column for posting code. Thanks!
  Reply

My Java solution (100%)

public static int solution(int N) {

String[] bitsBinaryN = Integer.toBinaryString(N).split("");

int maxBinaryGap = 0;

int currentBinaryGap = 0;

for (String n : bitsBinaryN) {

if (n.equals("0")) {

currentBinaryGap++;

} else {

currentBinaryGap = 0;

maxBinaryGap = currentBinaryGap > maxBinaryGap ? currentBinaryGap : maxBinaryGap;

}

return maxBinaryGap;

}

NOTE from admin: there is a bug. Rajashekar’s following comment fixes it.

for (String n : bitsBinaryN) {

if (n.equals("0")) {

currentBinaryGap++;

} else {

maxBinaryGap = currentBinaryGap > maxBinaryGap ? currentBinaryGap : maxBinaryGap;

currentBinaryGap = 0;

}

return maxBinaryGap;

function solution(N) {

// write your code in JavaScript (Node.js 4.0.0)

var str = N.toString(2);

str = str.replace(/0/g,' ').trim();

var groups = str.split('1');

if(groups.length == 0) return 0;

var gaps = groups.map(function(g){

return g.length;

});

return gaps.sort()[gaps.length -1];

}

Braulio says:
August 23, 2016 at 1:36 pm
using a regular expression: https://codility.com/demo/results/trainingYN5VZA-VPM/
Reply
objcGuy says:
August 25, 2016 at 11:16 am
Objective-c solution: Can you comment on Big O Notation Complexity of my solution please?
https://codility.com/demo/results/trainingJX2NTY-WEF/
Reply
- Sheng says:
  August 28, 2016 at 8:20 pm
  It should be O(log(N))
  Reply

// you can write to stdout for debugging purposes, e.g.

// console.log('this is a debug message');

function solution(N) {

// write your code in JavaScript (Node.js 6.4.0)

var b = N.toString(2);

var gap = 0, biggestGap = 0;

b.split('').forEach(function(el,i) {

if (el === "0") {

gap++;

}

else if (el === "1") {

if (gap > biggestGap) {

biggestGap = gap;

}

gap = 0;

}

});

return biggestGap;

}

Sheng says:
September 19, 2016 at 10:46 pm
Thanks for your contribution! Please also read the “Guideline for Comments” in the right column to post code.
Reply

Here is working 100% score with PHP 7

function solution($N) {

//Convert integer to binary and trim zeros on borders

$binary = trim(decbin($N), '0');

//Split binary to Array

$splitZeros = explode('1',$binary);

// Create array with value of the length for each string

$maxLength = array_map('strlen', $splitZeros);

return max($maxLength);

}

Python solution that gets 100%:

def solution(N):

binNum = bin(N)[2:]

result = 0

while binNum[0] == "0":

binNum = binNum[1:]

while binNum[len(binNum)-1] == "0":

binNum = binNum[:len(binNum)-1]

if "0" in binNum:

count = 0

for i in binNum:

if i == "0":

count += 1

if count > result:

result = count

else:

count = 0

return result

Here is mine solution using strings. My first Python program

def solution(N):

pos=0

max=0

s= str(bin(N))

start=0

while start!=-1:

start=s.find("10", pos)

if start==-1:

break

end=s.find("1", start+1)

if end==-1:

break

pos=end

l=end-start-1

if l>max:

max=l

return max

I think my solution is simple.

def solution(N):

max_gap = 0

current_gap = -32

while N > 0:

if N % 2 == 1:

current_gap = 0

else:

current_gap += 1

max_gap = max(max_gap, current_gap)

N //= 2

return max_gap

# you can write to stdout for debugging purposes, e.g.

# print("this is a debug message")

def solution(N):

# write your code in Python 3.6

binNumber = bin(N)

#print(binNumber, "--", binNumber[2:])

binNumber = binNumber[2:]

cntBinary = 0

maxBinary = 0

#print("Type of Object is--",type(binNumber))

for belem in binNumber:

if int(belem) == 0:

cntBinary+=1

#print("cntBinary", belem ,"--",cntBinary)

else:

if maxBinary < cntBinary:

maxBinary = cntBinary

cntBinary=0

#print("cntBinary", belem ,"--",cntBinary)

return int(maxBinary)

perfringo says:
February 9, 2018 at 2:53 am
It can be done as oneliner in Python. Not too great to read and understand but gets job done:
1
2
def solution(N):
return len(max(format(N, 'b').strip('0').split('1')))

Steps explained:
– convert int into binary (as suggested by Python official documentation)
– strip zeros (can be don also with rstrip)
– split at 1 (results a list of strings of zeros and empty strings)
– find max from list (as strings ’00’ > ‘0’ is True, then max returns longest string of zeros)
– find lenght of longest string of zeros
Reply

Hey Sheng,
I devised a simpler and faster code which handles trailing zeroes at the beginning of the logic itself.

def solution(N):

# first things first, remove trailing spaces present if any.

while not N%2:

N//=2

#calculate the binary gap now

binary_gap = 0

temp_counter=0

while N>0:

if not N%2:

temp_counter+=1

else:

if temp_counter>binary_gap:

binary_gap = temp_counter

temp_counter = 0

N//=2

return binary_gap

Java solution that gets 100%:

public int solution(int N) {

int temp = 0;

String bnry = Integer.toString(N, 2);

String[] parts = bnry.split("1");

int lenght = parts.length;

if (N % 2 == 0) {

lenght--;

}

for (int i = 0; i < lenght; i++) {

if (parts[i].length() > temp) {

temp = parts[i].length();

}

return temp;

}

int solution(int N) {

// write your code in C++14 (g++ 6.2.0)

std::string binary = bitset<64>(N).to_string();

int index_init =-1; int index_end = -1;

int sum = 0;

for(int i= 0; i <(int) binary.length(); i++){

if(binary[i] != '0'){

if(index_init != -1){

index_end = index_init;

if(i - index_end > sum) sum = i - (index_end + 1);

}

index_init = i;

}

return sum;

}

In C++:

int solution(int N) {

bool gap = false;

int gaplen = 0;

int maxgap = 0;

int lastbit = 0;

while (N) {

bool bit = N & 1;

gap = (lastbit && !bit) || (gap && !bit);

gaplen = gap ? ++gaplen : 0;

maxgap = std::max(maxgap, gaplen);

lastbit = bit;

N = N >> 1;

}

return maxgap;

}

in C#

class Solution {

public int solution(int N) {

// write your code in C# 6.0 with .NET 4.5 (Mono)

var s = Convert.ToString(N, 2);

var gap = 0;

var biggestGap = 0;

var i = 0;

while (i < s.Length)

{

if (s[i] == '0')

gap++;

if (s[i] == '1')

{

if (gap > biggestGap)

{

biggestGap = gap;

}

gap = 0;

}

i++;

}

return biggestGap;

}

i have simple solution and get 100

def solution(N):

# write your code in Python 3.6

biner = bin(N)[2:]

max = 0

count = 0

for i in biner:

if max<count and i=='1':

max=count

if i == '1':

count = 0

else:

count += 1

return max

Jeronimo Carrizo says:
June 3, 2019 at 4:57 am
My Solution with 100% with JS
function solution(N) { let cntZero = 0; let binarry = (N).toString(2); let gapsCount = []; let startGap = false;
for(const binary of binarry) { if (binary === '1' && !startGap) { startGap = true; } else if (binary === '1' && startGap) { gapsCount.push(cntZero); cntZero = 0; } else if (binary === '0' && startGap) { cntZero++; } } return gapsCount.sort().pop() || 0; }
Reply

My code 100% JavaScript

function solution(N) {

var a = N.toString(2);

var b = a.length;

var c = 0;

var max = 0;

var d = 0;

for (var i = 1; i < b; i++)

{

if (a.charAt(i) == 0)

{

c++;

}else{

if (max < c)

{

max = c;

}

c = 0;

d++;

}

if (d == 0)

{

return 0;

}else{

return max;

}

My solution for python

https://app.codility.com/demo/results/trainingZ46BJU-K44/

def BinGap(N):

a=bin(N).strip('0b')

b=a.split('1')

c= len(b)

d= [0] * 1000

for i in range(c-1) :

if b[i] !='':

d[i]= str(b[i]).count('0')

return max(d)

Selvaganapathy Duraiswamy says:
November 25, 2019 at 11:33 pm
Solution in GO :
https://app.codility.com/demo/results/trainingCHB2Q4-AAB/
Reply
Mustafa Kirimli says:
December 24, 2019 at 5:03 am
1
2
3
4
5
import re

def solution(N):
res = re.findall(r'([0]+)[1-9]', bin(N)[1:])
return len(max(res)) if len(res) > 0 else 0

Reply
Mustafa Kirimli says:
December 24, 2019 at 5:18 am
1
2
3
4
import re

def solution(N):
return len(max(re.findall(r'([0]+)[1-9]', bin(N)), default=''))

https://app.codility.com/demo/results/training2739DQ-KW5/
Reply

Javascript solution
https://app.codility.com/demo/results/trainingKSCP3M-DME/

function solution(N) {

// write your code in JavaScript (Node.js 8.9.4)

let bin = N.toString(2)

let binArray = [...bin]

let temp = 0

let binaryGap = 0

binArray.forEach(item => {

if (item == 0) {

binaryGap += 1

} else if (item == 1) {

if(temp < binaryGap) {

temp = binaryGap

}

binaryGap = 0

}

})

return temp

}

If you consider that a binary number as a string delimited by 1, this is a trivial

def solution_bin_gap(A):

a = '{0:b}'.format(A)

maxp = 0

parts = a.split('1')

for p in parts:

if len(p) > maxp:

maxp = len(p)

print (f'{a} has {maxp} zeros')

return maxp

100% Please check once
https://app.codility.com/demo/results/trainingBKCFZP-7CH/

def solution(N):

binary=bin(N).replace("0b","")

idx=[]

c=0

for i in binary:

c+=1

if i == "1" :

idx.append(c)

diff=[j-i for i, j in zip(idx[:-1], idx[1:])]

if len(idx) > 1:

gap=max(diff)-1

else:

gap=0

return gap

Hi everyone!
I did the following and got a 100%.
https://app.codility.com/demo/results/trainingE5KBTC-6GQ/

def solution(N):

# write your code in Python 3.6

b = get_binary(N)

if b==-1:

print('Invalid input')

if isinstance(b, str):

b_gap = max([len(x) for x in b.strip('0').split('1')])

return b_gap

def get_binary(N):

if not isinstance(N, int):

return -1

if N==0:

return '0'

r = 0

q = N

b = ''

while q!=1:

r = q%2

b += str(r)

q = q//2

b += str(q)

return b[::-1]

Patrick says:
May 11, 2022 at 12:35 am
Python code and it was 100%
1
max([len(i) for i in bin(N).replace("0b", "").split("1")[:-1]])

Reply

85 Replies to “Solution to Binary-Gap by codility”

Leave a Reply to w7gf83fgiwyfg Cancel reply