'Finding biggest binary gap

I have to find the binary gap for an integer number.

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: N = 1041 binary:10000010001 Result: 5 (5 zeros surrounded by ones)

Below is my code, although bin_no[22] is 1 but it never goes inside if statement.

def solution(N):
    bin_no = f'{N:32b}'
    print(len(bin_no))
    count = []

    for i in range(len(bin_no)):
        if bin_no[i] == 1:
            count[i] = 0
            j=i
            while(bin_no[j+1] != 1):
                count[i] +=1
                j +=1
            print (count[i])

print(solution(529))


Solution 1:[1]

Simple and fast

def solution(N):
    binary = bin(N)[2:].strip("0").split("1")
    return max(len(x) for x in binary)

Solution 2:[2]

use regex:

def solution(N):
    bin_no = f'{N:b}'
    pt= r"10+(?=1)"
    mtchs = re. findall(pt, bin_no)
    print(bin_no)
    print(mtchs)
    mx = max(mtchs,key=len)
    return mx.count('0')

print(solution(401))

output:

110010001

['100', '1000']

3

Solution 3:[3]

I have a solution in Java.

class BinaryGap {
    public static void main (String args[])
    {
        BinaryGap binaryGap = new BinaryGap();
        int n = 261;
        System.out.println("Max count : "+binaryGap.binaryValue(n));
    }
    
    public int binaryValue(int N) {
        String binaryValue = Integer.toBinaryString(N);
        System.out.println("binaryValue : "+binaryValue);
        int maxZeroCount = 0;
        int zeroCount = 0;
        for (int i = 0, n = binaryValue.length(); i < n; i++) {
            if(binaryValue.charAt(i) == '0') {
                ++zeroCount;
            } else {
                if(zeroCount > maxZeroCount) {
                    maxZeroCount = zeroCount;
                }
                zeroCount = 0;
            }
        }
        return maxZeroCount;
    }
}

Solution 4:[4]

Here is another efficient solution. Hope it may helps you. You just need to pass any number in function and it will return longest Binary gap.

def Solution(num):

n = int(num/2)
bin_arr = []

for i in range(0,n):
    if i == 0:
        n1 = int(num/2)
        bin_arr.append(num%2)
    else:
        bin_arr.append(n1%2)
        n1 = int(n1/2)

        if n1 == 0:
            break

print(bin_arr)
result = ""
count = 0
count_arr = []

for i in bin_arr:
    if result == "found":
        if i == 0:
            count += 1
        else:
            if count > 0:
                count_arr.append(count)
                count = 0
    if i == 1:
        result = 'found'
    else:
        pass

if len(count_arr) == 0:
    return 0
else:
    return max(count_arr)

print(LongestBinaryGap(1130))  # Here you can pass any number.

Solution 5:[5]

You can split zeroes with '1' and get groups of zeroes as a list. Find the longest and it's done!

def solution(N):
    bin = f'{N:b}'  # for 32-bit representation with leading zeroes use f'{N:#032b}'
    splitted = bin.split('1')
    m = max(splitted, key=len)
    return len(m)

So it goes like this:

1041 -> '10000010001' -> ['', '00000', '000', ''] -> '00000' -> 5

The code can be easily changed to ignore leading and trailing group of zeroes if that's your case.

Solution 6:[6]

f'{n:b}' support in python v3.6+

def solution(N):
    return len(max(f'{n:b}'.strip('0').split('1')))
  1. convert number to binary with f'{n:b}'.
  2. remove all zeros from left and right with strip('0').
  3. convert string to zeros list ex:['00', '000'] with split('1').
  4. get the max length element in the list with max(list).
  5. return the length of the element with return len(element)

Solution 7:[7]

PHP Version:

function solution($N) {
$binary = decbin($N);
$array_binary = array_map('intval', str_split($binary));
$counter_gaps = 0;
$longest = 0;

foreach($array_binary as $key => $value){
    if($value == 1 && $key > 1){
        $longest = $counter_gaps > 0 && $counter_gaps > $longest ? $counter_gaps : $longest;
        $counter_gaps = 0;
    }else if($value == 0 && $key >= 1){
        $counter_gaps++;
    }
}
return $longest; 

}

print_r(solution($N));

Solution 8:[8]

I have 2 C# solutions.

@Kwaku Manu Amponsem Answer in C#

public int solution(int N) {
        string binary = Convert.ToString(N,2);
        var abc  = binary.Trim('0').Split('1');
        int max = abc.Select(x=> x.Length).Max();
        return max;
    }

Other Solution

 public int solution(int N)
        {
            try
            {
                int result = 0;
                if (N <= 0)
                {
                    return result;
                }
                else
                {
                    string binary = Convert.ToString(N, 2);
                    int count = 0;
                    for (int i = 0; i < binary.Length; i++)
                    {
                        if (binary[i] == '1')
                        {
                            if (result < count)
                                result = count;
                            count = 0;
                        }
                        else
                        {
                            count++;
                        }
                    }
                }
                return result;
            }
            catch (Exception e)
            {
                return 0;
            }
        }

Solution 9:[9]

def solution(N):
   y = "{0:b}".format(N).split('1')
   if y.count('') == len(y):
       return 0
   if y[0] == '0' or '1' not in y[0]:
       y[0] = ''
   if y[-1] == '0' or '1' not in y[0]:
       y[-1] = ''    
   x = list(filter(None, y))
   return max(map(lambda a: len(a), x)) if len(x) > 0 else 0

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 Kwaku Manu Amponsem
Solution 2
Solution 3 Amal Mathew
Solution 4 Raza ul Mustafa
Solution 5
Solution 6
Solution 7
Solution 8
Solution 9 Lawal Rahman Abimbola