'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 inpython 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']
withsplit('1')
. - get the max length element in the list with
max(list)
. - 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 |