Solution to Binary-Gap by codility

29 Jan

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

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%: https://codility.com/demo/results/trainingBUPAMC-8KR/

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

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

      is ALWAYS true. Why do you need it?

  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.

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

  28. My code 100% JavaScript

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

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

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

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

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!