Problem

A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N.

For example, number 9 has binary representation 1001 and contains a binary gap of length 2. The number 529 has binary representation 1000010001 and contains two binary gaps: one of length 4 and one of length 3. The number 20 has binary representation 10100 and contains one binary gap of length 1. The number 15 has binary representation 1111 and has no binary gaps. The number 32 has binary representation 100000 and has no binary gaps.

Write a function:

    function solution($N);

that, given a positive integer N, returns the length of its longest binary gap. The function should return 0 if N doesn't contain a binary gap.

For example, given N = 1041 the function should return 5, because N has binary representation 10000010001 and so its longest binary gap is of length 5. Given N = 32 the function should return 0, because N has binary representation '100000' and thus no binary gaps.

Write an efficient algorithm for the following assumptions:

    • N is an integer within the range [1..2,147,483,647]. 

Notes

Note that 2,147,483,647 is approximately = 2³¹, which is the maximum integer size for most PHP compilers.

The brute-force (direct) way to do this is to convert the decimal number to a string of 1's and 0’s, then look for the binary gaps, and then count the zeros of the longest gap.

A different method, the one used here, continuously divide the decimal number, by 2; and then reading the result from the bottom, as the following table illustrates, for the decimal number, 529:

Read from the bottom, the answer is, 1000010001. For any division step, there is the dividend divided by the divisor, to give the quotient. The quotient always has a whole number and a remainder. The remainder, may be zero. When converting to base 2, the last quotient is always, zero remainder 1. This 1 is actually the first digit (on the left) of the base 2 equivalent number.

The brute force method takes too long. A faster way to solve the problem, as used here, is to begin by assuming that the length of the longest binary gap is 0. This value is stored in a variable. And then while converting to binary, the zeros are counted. When a binary gap is detected, the number of zeros is stored as the maximum gap length, replacing the stored zero. If the next binary gap is longer than this one, then this stored value is replaced by that longer value. If no binary gap is detected in the whole process while converting to binary, then the stored value remains zero.

The Script Solution

The script is as follows. Read the comments and note how the fact that the first remainder may not be 1, has been taken into consideration, with the Boolean variable, metFirstOne.

<?php
    function solution($N) {
        $store = 0;
        $count = 0;  //counting begins from zero
        $metFirstOne = false;  //boolean; counting is effective only after the first 1 has been met

        while ((int)($N/2) >= 0) {  //whole number part of quotient
            $R = $N%2;    //modulo to obtain remainder
            
            if ($R == 1) {
                if ($count > $store && $metFirstOne == true) {
                    $store = $count;
                    $count = 0;  //reinitialize counter for next possible gap
                }
            }
            
            if ($R == 0)     //remainder is 0
                $count = $count + 1;
            else {
                $metFirstOne = true;
                $count = 0;  //reinitialize counter for next possible gap
            }
            
            if ($N==0)
                break;
            $N = (int)($N/2);
        } 
        
        return $store;
    } 

    $N = 9; 
    $ret1 = solution($N); 
    echo $ret1."\n";

    $N = 529; 
    $ret2 = solution($N); 
    echo $ret2."\n";

    $N = 20; 
    $ret3 = solution($N); 
    echo $ret3."\n";
    
    $N = 15; 
    $ret4 = solution($N); 
    echo $ret4."\n";
    
    $N = 32; 
    $ret5 = solution($N); 
    echo $ret5."\n";

    $N = 1041; 
    $ret6 = solution($N); 
    echo $ret6."\n";
?>

Note that the calling function is not typed at app.codility.com/programmers (not sent to the server).

There are three if-constructs. The first if-construct should not be typed after the second if-construct.

There are 6 test cases in the above script. The output for the 6 test cases is:

    2
    4
    1
    0
    0
    5

The last if-construct stops (breaks) the loop, when the whole number part of the quotient is zero.

Conclusion

The brute-force (direct) way to solve the above problem, is to convert the decimal number to a string of 1's and 0's, then look for the binary gaps, and then count the zeros of the longest gap. The brute force method takes too long.

A faster way to solve the problem, is to begin by assuming that the length of the longest binary gap is 0. This value is stored in a variable. And then while converting to binary, the zeros are counted. When a binary gap is detected, the number of zeros is stored as the maximum gap length, replacing the stored zero. If the next binary gap is longer than this one, then this stored value is replaced by that longer value. If no binary gap is detected in the whole process, while converting to zero, then the stored value remains zero.

The reader should register at app.codility.com/programmers to be testing his/her own code. At app.codility.com/programmers the PHP main() function is not submitted.