Solution to Binary-Gap by codility

29 Jan


Question Name: BinaryGap

85 Replies to “Solution to Binary-Gap by codility

  1. 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!

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

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

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

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

  3. My php solution, 100% ๐Ÿ˜€

    • Even more simpler with PHP:)

  4. My C solution, 100%:

  5. Here is my javascript solution

    • Why do you need all this stuff? What are you trying to check?

      is ALWAYS true. Why do you need it?

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

  6. What do you think about this solution

  7. Javascript Solution

    • C# solution with Regex and Split

  8. //java one

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

  10. why when n=51712 the answer should be 2 not 9?
    >>> bin(51712)
    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

  11. 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?

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

  12. Hi Sheng, here is my solution in Javascript.

  13. Here’s my 100% C# solution.

  14. Here’s a C# solution using bit shifting.

  15. My 100% C# solution

  16. My Java solution (100%)

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

  17. Here is working 100% score with PHP 7

  18. Python solution that gets 100%:

  19. Here is mine solution using strings. My first Python program

  20. I think my solution is simple.

  21. It can be done as oneliner in Python. Not too great to read and understand but gets job done:

    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

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

  23. Java solution that gets 100%:

  24. In C++:

  25. in C#

  26. i have simple solution and get 100

  27. 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) {
    cntZero = 0;
    } else if (binary === '0' && startGap) {
    return gapsCount.sort().pop() || 0;

  28. My code 100% JavaScript

  29. Javascript solution

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

  31. 100% Please check once

  32. Hi everyone!
    I did the following and got a 100%.

Leave a Reply

Your email address will not be published.

Please put your code into a <pre>YOUR CODE</pre> section. Thanks and Happy Coding!