Binary Gap - Leetcode Solution

Problem Statement:

Given a positive integer n, find and return the length of the longest binary gap of the binary representation of n. If there is no binary gap, return 0.

A binary gap is defined as the maximum sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of a number.

Input: n = 22 Output: 2 Explanation: The binary representation of 22 is 10110, where there are two binary gaps: 1. The first gap with length 1 occurs between the first two ones. 2. The second gap with length 2 occurs between the last two ones.

Approach:

We can approach this problem by converting the given integer number into its binary form. After we have the binary form, we can then check for consecutive zeros between the two ones that surround it. If the number of consecutive zeros is greater than the maxLength variable we have initialized, we will update the maxLength variable.

Algorithm:

1. Initialize maxLength as 0
2. Convert integer n into binary representation using the bin() function in Python.
3. Remove the '0b' prefix from the binary representation.
4. Iterate through the binary string and keep track of consecutive zeros. a. If the current bit is '0', increment the count of consecutive zeros. b. If the current bit is '1', and the consecutive zeros count is greater than maxLength, update maxLength with the count of consecutive zeros. c. Reset the count of consecutive zeros after each 1.
5. Return maxLength.

Code:

def binaryGap(n: int) -> int:
    binary = bin(n)[2:]
    maxLength = 0
    count = 0
    
    for i in range(len(binary)):
        if binary[i] == '0':
            count += 1
        
        if binary[i] == '1':
            if count > maxLength:
                maxLength = count
            count = 0
    
    return maxLength

Time Complexity: O(log n) Space Complexity: O(log n)

1