Solution to Binary-Gap by codility

29 Jan

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

Question Name: BinaryGap

53 thoughts on “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% 😀

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

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

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

  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?
    Thanks!

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

Leave a Reply

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