Finding biggest binary gap

Question

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

You confuse numbers and characters. Compare to `'1'`, not to `1`. — DYZ, May 28 '20 at 17:58
Somewhat tangential to what you're asking but note that Python has a built-in function `bin`, for converting integers to their binary representation; with that, you don't have to pad with spaces, and could convert each binary digit to an integer, in case you prefer comparison with those; that'd be something like `for binary_digit in map(int, bin(529)[2:]) ... if binary_digit == 1 ...` — fuglede, May 28 '20 at 18:02
You are comparing a digit to a character. Here is a good solution in python. https://stackoverflow.com/questions/48951591/python-find-longest-binary-gap-in-binary-representation-of-an-integer-number — Nico Müller, May 28 '20 at 18:10
Does this answer your question? [Python: Find longest binary gap in binary representation of an integer number](https://stackoverflow.com/questions/48951591/python-find-longest-binary-gap-in-binary-representation-of-an-integer-number) — Henke, Aug 14 '21 at 17:48

score 5 · Answer 1 · answered Sep 28 '20 at 14:29

5

Simple and fast

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

answered Sep 28 '20 at 14:29

Kwaku Manu Amponsem

51
1
2

moyoumos · Answer 2 · 2020-05-29T14:22:02.173

1

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

edited May 29 '20 at 14:22

answered May 29 '20 at 11:02

moyoumos

17
3

score 1 · Answer 3 · answered Feb 23 '21 at 17:57

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;
    }
}

Welcome to Stackoverflow and thank you for your effort. However this question is a python tagged question, so your answer is technically off-topic. Try and provide a solution that answers the question in python. — nCessity, Feb 23 '21 at 22:37

score 1 · Answer 4 · answered Jun 07 '21 at 10:16

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.

asikorski · Answer 5 · 2020-05-29T11:30:20.980

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.

Mahmoud Adel · Answer 6 · 2021-12-17T08:16:43.870

0

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

def solution(N):
    return len(max(f'{n:b}'.strip('0').split('1')))

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

edited Dec 17 '21 at 08:16

answered Dec 16 '21 at 20:52

Mahmoud Adel

1
5

Your answer could be improved with additional supporting information. Please [edit] to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers [in the help center](/help/how-to-answer). – Community Dec 17 '21 at 01:37

Filipe Eusébio · Answer 7 · 2022-01-18T21:29:46.000

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

Muhammad Asad · Answer 8 · 2022-04-17T11:25:49.277

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;
            }
        }

score 0 · Answer 9 · answered May 03 '22 at 12:38

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

score 0 · Answer 10 · answered Sep 15 '22 at 10:10

def solution(N):
    get_bin = lambda x: format(x, 'b')
    return len(max(get_bin(N).strip("0").split("1")))

explanation:

get_bin: gets a binary formatted version of bin() function.
since the question asked number of 0's that are wrapped by 1's, strip the string by 0.
now split text by using 1 and get the max string
finally get the max strings length and return it

score 0 · Answer 11 · answered Oct 04 '22 at 12:15

In PHP

function solution($N) {
    // write your code in PHP7.0
    $bin_num = decbin($N);
    // Remove leading 0
    $bin_num = ltrim($bin_num, 0);
    // Remove ending 0
    $bin_num = rtrim($bin_num, 0);

    $num_arr = explode('1', $bin_num);
    $arr_val = array();
    foreach($num_arr as $val){
        $arr_val[] = strlen($val);
    }
    return max($arr_val);
}

Finding biggest binary gap

11 Answers11