Binary Gap

The task is to find the longest distance between any two adjacent 1’s in the binary representation of a given integer ( n ). If there are no two adjacent 1’s, we’ll return 0.

Approach

  1. Convert to Binary: Convert the given integer ( n ) to its binary representation.
  2. Initialize Variables: Initialize variables to keep track of the maximum distance and the last seen position of 1.
  3. Iterate through the Binary Representation: Iterate through the binary string and do the following: a. If a ‘1’ is found, calculate the distance from the last ‘1’ and update the maximum distance if this distance is larger. b. Update the last seen position of 1.
  4. Return Result: Return the maximum distance found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def binaryGap(self, n: int) -> int:
        binary_representation = bin(n)[2:] # Convert to binary, skip '0b' prefix
        max_distance = 0
        last_one_pos = -1

        for i, bit in enumerate(binary_representation):
            if bit == '1':
                if last_one_pos != -1:
                    max_distance = max(max_distance, i - last_one_pos)
                last_one_pos = i

        return max_distance

Example

  • For n = 22, the binary representation is “10110”. The distances between adjacent 1’s are 2 and 1. So the output is 2.
  • For n = 8, the binary representation is “1000”. There are no adjacent 1’s, so the output is 0.
  • For n = 5, the binary representation is “101”. The distance between adjacent 1’s is 2, so the output is 2.

Complexity

The time complexity of this solution is ( O(\log n) ), where ( n ) is the input integer. This is due to the binary conversion and iteration over the binary representation. The space complexity is ( O(1) ) since we only use a constant amount of extra space.