Solution to Binary-Gap by codility

29 Jan


Question Name: BinaryGap

66 Replies to “Solution to Binary-Gap by codility

    • Yes, your solution is good. Actually my solution is kind of bad. I should use more bit operations rather than math operations.

  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%:

Leave a Reply

Your email address will not be published. Required fields are marked *

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