Question

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.
E.g.:
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.
Write a function: class Solution { public int binary_gap(int 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.

Answer 1

this seems pretty hard of a problem

Answer 2

just thinking aloud, I would approach it along the lines of:

maxGap = 0
inGap = false
while N > 0
if N % 2 == 1
if inGap AND gapLength > maxGap
maxGap = gapLength
inGap = true
gapLength = 0
else:
gapLength++
N = N >> 1

return maxGap

Answer 3

I made this program in python (just create a file with ".py" in the end put the code in it and use "python nameOfFile.py number", where 'number' can be any integer):
"""
Get the Max Gap
"""
import sys
import re

if __name__ == '__main__':
number = int(sys.argv[1])
binNumber = bin(number)
strBinNumber = binNumber.__str__()
strBinNumber = re.split("0b", strBinNumber)[1]

maxGap = 0
counter = 0
firstFound = False
for c in list(strBinNumber):
if c == '1':
firstFound = True
if maxGap < counter:
maxGap = counter
counter = 0
else:
if firstFound:
counter+=1
print(strBinNumber)
print(maxGap)

Answer 4

Thank you very much all of you, I can't give 2 medals but @asnasser I'll prepare one for you on the next one. Thanks much.

Answer 5

yw :)

Answer 6

I made this program in Java
public int maxBinaryGap(int number) {
int maxGap = 0;
boolean inGap = false;
int gapLength = 0;

while (number > 0) {
if (number % 2 == 1) {
if (inGap && gapLength > maxGap) {
maxGap = gapLength;
}
inGap = true;
gapLength = 0;
} else {
gapLength++;
}
number = number >> 1;
}
return maxGap;
}